1 Prerequisites

Before we even start, it is of crucial importance to first understand deeply linear and logistic regression. This is because (as we will see in later discussion) they are the very basic components in a general neural network model.

1.1 Linear Regression

A linear model can be written in a matrix form

\[ Y = X\beta + \epsilon, \] where \(Y\) is the output or label vector of length \(N\) (number of observations), \(X\) is the input feature matrix (referred to as the design matrix in statistics) with dimension \(N\) by \(P\) (number of features), \(\beta\) is the model weights/coefficients (a column vector of length \(P\)) for which we’d like to solve, \(\epsilon\) is the model residual or error vector.

1.1.1 Ordinary Least Squares

The classical way to solve for \(\beta\) is ordinary least squares. The idea of OLS is find out the weights that minimize the mean of squared model errors:

\[ \begin{aligned} \mbox{mse (loss)} &= \frac{1}{N}\sum_i\epsilon^2_i \\ &= \frac{1}{N}\sum_i(y_i - \beta x_i)^2, \end{aligned} \]

where \(y_i\) and \(x_i\) is the \(i\)-th observation. The first-order condition (requiring that the first-order derivative w.r.t. weights are zero) gives us the OLS solution for model weights \(\beta\) analytically (in matrix notation):

\[ \begin{equation} \label{eq:ols} \hat{\beta} = (X'X)^{-1}X'Y. \end{equation} \]

Let’s consider a toy model with only one non-constant feature:

\[ y_i = 6 + 4x_i + \epsilon_i. \]

In this model the outcome \(y\) is determined by a bias term plus a single variable \(x\), with an independently distributed noise term \(\epsilon \sim \mbox{Normal}(0, 1)\).

Create some random data generated from this model:

[[ 1.         -0.46820879]
 [ 1.         -0.82282485]
 [ 1.         -0.0653801 ]
 [ 1.         -0.71336192]
 [ 1.          0.90635089]
 [ 1.          0.76623673]
 [ 1.          0.82605407]
 [ 1.         -1.32368279]
 [ 1.         -1.75244452]
 [ 1.          1.00244907]]

Without consideration of the noise term, the OLS estimator will solve precisely for the true model weights:

[6. 4.]

Of course in the real world the noise term cannot be determined and usually the feature alone cannot explain entirely the variation in the outcome. This means that what we actually estimate will be the expected value of model weights:

[6.01132196 3.96247175]

By the Law of Large Number and Central Limit Theorem, the OLS estimator will converge in probability to the true model weights and distributed asymptotically Normal in large sample.1

The issue of the above approach is that equation \(\eqref{eq:ols}\) is not numerically stable when it comes to large-scale application where we may have lots of observations and lots of features. One very useful solution to solve the estimator numerically in large-scale application is the gradient descent approach.

1.1.2 Gradient Descent with Mean Squared Error

Instead of solving the first-order condition analytically, we can do it numerically. Gradient descent is a 1st-order optimization technique to find local optimum of a given function.

In the model training exercise our target function is the loss so the optimization problem is:

\[ \operatorname*{argmin}_\beta \mbox{Loss} = \frac{1}{N}\sum_i(y_i - \beta x_i)^2. \]

That is, we’d like to figure out model weights that minimize the loss which is defined by the mean squared errors when the model is a regression model.

The idea of gradient descent is to

  1. Derive the functional form of the gradient of loss w.r.t. to all weights
  2. Initialize all model weights randomly
  3. Calculate the gradient value using the actual data and the current value of weights
  4. Update the weights by (partially) the amount of gradient just calculated
  5. Repeat 3 and 4 until the resulting gradients become small enough

Let’s use the toy example to actually implement a gradent descent optimizer from scratch. First we re-write the loss function explicitly with our setup of one coefficient with a constant (\(\beta = [\beta_0, \beta_1]\)):

\[ \mbox{Loss} = \frac{1}{N}\sum_i\big[y_i-(\beta_0 + \beta_1x_i)\big]^2. \]

Now the gradient (or equivalently the 1st-order derivative) w.r.t. to weights will be:

\[ \begin{aligned} \frac{\partial\mbox{Loss}}{\partial\beta_0} &= - \frac{2}{N}\sum_i \big[ y_i - (\beta_0 + \beta_1x_i) \big], \\ \frac{\partial\mbox{Loss}}{\partial\beta_1} &= - \frac{2}{N}\sum_i \big[ y_i - (\beta_0 + \beta_1x_i) \big]x_i. \end{aligned} \]

The corresponding python function can be coded as:

If we set the above equations to zero we can solve for \(\beta_0\) and \(\beta_1\) analytically and the solution will be exactly just equation \(\eqref{eq:ols}\). But as we just pointed out it suffers from numerical stability issue.

The minimum implementation of our gradient descent optimizer is just a few lines:

[6.01132196 3.96247175]

As we can see the result is very closed to our analytical solution.

On Learning Rate

Learning rate is a hyper-parameter for gradient descent optimizer. The gradient update to our model weights is scaled down by the learning rate to make sure convergence. Too large the learning rate will explode the gradient. Too small the learning rate will slow down the convergence and sometimes result in the optimizer trapped at local sub-optimum.

Let’s re-write our gradient descent optimizer to also track the loss from each training step. And we use the same initialization for a fair comparison.

Now we run the optimization with a variety of different learning rates. For illustration purpose we will only run a few steps.

Learning Rate 0.001 | Estimate: [0.18155223 0.12379996]
Learning Rate  0.01 | Estimate: [1.60013258 1.08670659]
Learning Rate  0.05 | Estimate: [4.81547513 3.22246947]
Learning Rate   0.1 | Estimate: [5.81500752 3.85150789]
Learning Rate     1 | Estimate: [19.8158439  18.42703331]

The result suggests that a learning rate of 1 is too large for our problem. The gradient explodes which make our solution diverge. And a lower learning rate in general converges slower to the optimum. Number of examples used to calculate the gradient also will affect the convergence behavior. In general if the sample size is too small a smaller learning rate should be used to avoid gradient explosion.

This can be more clearly seen if we plot the trace of our training losses:

If the loss doesn’t decrease over training iteration, it is a signal that something is wrong with our model.

Unlike our toy implementation, in modern implementation of any numerical optimizer there will be a lot of techniques to do the best to avoid convergence failure. But it is the model developer’s responsibility to diagnose the training behavior before anything is delivered to the stakeholder. Checking the dynamics of loss is usually the first and quick step to examine whether the training task is functioning as expected.

Batch Gradient Descent

The vanilla gradient descent optimizer we just implemented has one issue. Since for each update it needs to traverse over the entire dataset, it becomes too slow when it comes to large dataset.

Batch gradient descent is too overcome this issue. Instead of calculate the gradient using the entire dataset, we can use only a random subset of it. It will be less precise but statistically the result will be consistent.

Let’s implement a batch gradient descent optimizer:

[5.98189269 3.94839182]

Batch optimizer is currently the best practice of training neural networks in large scale application. The batch size depends on the actual application but usually ranges from 8 to 1024.

Stocahstic Gradient Descent

If we set the batch size as exactly 1, i.e., to calculate the gradient update only use one data observation at a time, this is referred to as stochastic gradient descent.

Here we introduce the term epoch: One epoch is for the optimizer to traverse the entire dataset once (no matter how many examples are used to calculate the gradient in each update). Number of epochs can be considered as another hyper-parameter of a model. We can also implement epoch in our previous batch gradient descent optimizer but for simplicity we ignore that. Let’s implement it in our SGD optimizer:

[5.98165419 3.88881224]

Plot the losses for the first 500 updates.

Unlike the vanilla gradient descent, stochastic gradient descent doesn’t ensure the loss is always decreasing. But statistiaclly it should converge to the same solution as the vanilla approach.

1.2 Logistic Regression

A logistic regression models the outcome probablistically:

\[ \begin{equation} \label{eq:logit} P(Y = 1) = \frac{1}{1 + e^{-X\beta}}, \end{equation} \]

Here the sigmoid function \(s(t) = \frac{1}{1 + e^{-t}}\) is used to transform a real number into probability space \([0, 1]\).

We can interpret the model as a linear model in log-odds. Assuming Y is binary and take a value of 0 or 1, the odds of \(Y = 1\) is defined as \(\frac{P(Y = 1)}{P(Y = 0)} = \frac{P(Y = 1)}{1 - P(Y = 1)}\). We can re-arrange the logistic model equation:

\[ \begin{aligned} \ln \Bigg[ \frac{P(Y = 1)}{1 - P(Y = 1)} \Bigg] &= \ln \Bigg[ \frac{\frac{1}{1 + e^{-X\beta}}}{\frac{e^{-X\beta}}{1 + e^{-X\beta}}} \Bigg] \\ &= \ln(1 + e^{-X\beta}) - \ln e^{-X\beta}(1 + e^{-X\beta}) \\ &= \ln(1 + e^{-X\beta}) - \ln e^{-X\beta} - \ln(1 + e^{-X\beta}) \\ &= - \ln e^{-X\beta} \\ &= X\beta. \end{aligned} \]

That is, the model weights are linear in the log-odds of our target outcome.

When the probability is transformed into odds, the range is transformed from \([0,1]\) to \([0,\infty]\).

If we further transform odds to log-odds, the range is transformed from \([0,\infty]\) to \([-\infty,\infty]\).

Put it together is the effect of the sigmoid function:

1.2.1 Cross Entropy

How do we solve for the model weights \(\beta\) in equation \(\eqref{eq:logit}\)? In the linear regression model we solve for the weights by minimizing the mean squared error. In logistic regression model we need to define measurement for modeling error as well.

Put it differently, we’d like to calculate the distance between our predicted probability and the real event label distribution (called the empirical distribution). In information theory the cross entropy is used to measure the distance between two probability distribution.

The entropy of a discrete probability distribution is defined as:

\[ H(p) = - \sum_i p_i \log_2p_i, \]

where \(p_i\) is the probability for event \(i\). It measures the uncertainty of a stochastic event.

Take a coin flip event as example. We plot the entropy value at different value of coin bias (the probability of having a head instead of a tail.)

It is obvious that the entropy of this event is maximized when the probability of flipping a head is exactly 0.5. At this level the event has a highest level of uncertainty in a sense that it is the most difficult case to predict the outcome of a flip.

Now move on to cross entropy. Cross entropy between two discrete probability distribution \(p\) and \(q\) over the same support is defined as:

\[ H(p, q) = - \sum_i p_i \log_2q_i. \]

For our logistic regression model, distribution \(p\) is the empirical distribution (label distribution) and distribution \(q\) is our model predicted distribution. Denote \(q_i = P(y_i = 1)\) for the prediction of \(i\)-th example. The cross-entropy-loss of our model hence can be written as:

\[ \mbox{Cross-Entropy Loss} = - \frac{1}{N}\sum_i^N \bigg[ y_i\log_2q_i + (1 - y_i)\log_2(1 - q_i)\bigg], \]

where \(y_i \in \{0,1\}\) is the \(i\)-th binary training label and \(P(y_i = 1)\) the model prediction for the \(i\)-th example out of \(N\) total training examples. This is the mean value of cross entropy for each training example.

Since \(q_i = P(y_i = 1)\) is expressed by our model equation \(\eqref{eq:logit}\), now we can apply gradient descent to the loss function to find out the optimum model weights that minimize the cross-entropy loss.

1.2.2 Maximum Likelihood Estimator

Before we implement our optimizer for a logistic regression model, we demonstrate that minimizing cross entropy is indeed equivalent to maximizing data likelihood.

The data likelihood is just the product of all predicted probabilities for individual example, provided that they are independent.

\[ \mbox{likelihood} = \prod_i^N q_i^{y_i}(1 - q_i)^{1 - y_i}. \]

The maximum likelihood estimator will try to maximize the log of the likelihood, which is:

\[ \begin{aligned} \mbox{log-lik} &= \log_2 \prod_i^N q_i^{y_i}(1 - q_i)^{1 - y_i} \\ &= \sum_i^N \log_2 q_i^{y_i}(1 - q_i)^{1 - y_i} \\ &= \sum_i^N \bigg[ y_i\log_2 q_i + (1 - y_i)\log_2(1 - q_i) \bigg]. \end{aligned} \]

By taking the average as well, the negative log-likelihood is exactly the cross entropy.

1.2.3 Gradient Descent with Log Loss

Now let’s also implement a batch gradient descent optimizer for a logistic regression model. We will use the same toy example and create additional random binary labels for this exercise.

The gradient function must be derived with respect to model weights. To simplify the math we replace log of base 2 with natural log (with no impact on the optimization), and we take advantage of the fact that the derivative of the sigmoid function is:2

\[ \begin{aligned} \frac{ds(t)}{dt} &= \frac{d\frac{1}{1 + e^{-t}}}{dt} \\ &= -(1 + e^{-t})^{-2} \cdot (- e^{-t}) \\ &= \frac{e^{-t}}{(1 + e^{-t})^2} \\ &= \frac{1}{1 + e^{-t}} \cdot \frac{e^{-t}}{1 + e^{-t}} \\ &= s(t) \cdot [1 - s(t)]. \end{aligned} \]

The gradient in our univariate model w.r.t. the bias term will be:3

\[ \begin{aligned} \frac{\partial\mbox{LogLoss}}{\partial\beta_0} &= - \frac{1}{N}\sum_i \bigg[ y_i\frac{\partial\ln q_i}{\partial\beta_0} + (1 - y_i)\frac{\partial\ln(1 - q_i)}{\partial\beta_0}\bigg] \\ &= - \frac{1}{N}\sum_i \bigg[ y_i\frac{1}{q_i}\frac{\partial q_i}{\partial\beta_0} + (1 - y_i)\frac{1}{1 - q_i}\frac{\partial(1 - q_i)}{\partial\beta_0}\bigg] \\ &= - \frac{1}{N}\sum_i \bigg[ y_i\frac{1}{q_i}\frac{\partial (\beta_0 + \beta_1x_i)}{\partial\beta_0}\frac{\partial q_i(t)}{\partial t} - (1 - y_i)\frac{1}{1 - q_i}\frac{\partial (\beta_0 + \beta_1x_i)}{\partial\beta_0}\frac{\partial q_i(t)}{\partial t}\bigg] \\ &= - \frac{1}{N}\sum_i \bigg[ y_i\frac{1}{q_i}q_i(1 - q_i) - (1 - y_i)\frac{1}{1 - q_i}q_i(1 - q_i)\bigg] \\ &= - \frac{1}{N}\sum_i \bigg[ y_i(1 - q_i) - (1 - y_i)q_i \bigg] \\ &= - \frac{1}{N}\sum_i (y_i - q_i). \end{aligned} \]

Similary for the weight:

\[ \frac{\partial\mbox{LogLoss}}{\partial\beta_1} = - \frac{1}{N}\sum_i (y_i - q_i)x_i. \]

Now the Python code for batch gradient descent with log-loss:

[2.7018906  1.37265212]

Comparing to linear regression, a logistic regression model is harder to converge. Since our naive implementation does not do convergence diagnostics, let’s use R’s built-in glm function which use Newton’s method (a 2nd-order optimizer utilizing not only 1st-order but also 2nd-order derivatives) to check the estimation result of our toy example:

(Intercept)           x 
   7.279770    4.913451 

Now increase both the learning rate and training step of our naive gradient descent optimizer:

[7.19221871 4.82282142]

Seems better.

Or we can use the Python package statsmodels (which also uses a 2nd-order optimizer by default) to check our result:

Optimization terminated successfully.
         Current function value: 0.097274
         Iterations 10
<class 'statsmodels.iolib.summary.Summary'>
"""
                           Logit Regression Results                           
==============================================================================
Dep. Variable:                      y   No. Observations:                 1000
Model:                          Logit   Df Residuals:                      998
Method:                           MLE   Df Model:                            1
Date:                Tue, 25 Jun 2019   Pseudo R-squ.:                  0.6480
Time:                        21:59:24   Log-Likelihood:                -97.274
converged:                       True   LL-Null:                       -276.32
Covariance Type:            nonrobust   LLR p-value:                 7.328e-80
==============================================================================
                 coef    std err          z      P>|z|      [0.025      0.975]
------------------------------------------------------------------------------
const          7.2798      0.721     10.100      0.000       5.867       8.692
x1             4.9135      0.534      9.195      0.000       3.866       5.961
==============================================================================

Possibly complete quasi-separation: A fraction 0.36 of observations can be
perfectly predicted. This might indicate that there is complete
quasi-separation. In this case some parameters will not be identified.
"""

Or we can use the popular machine learning library sklearn to do the same check:

array([[7.27975064, 4.91343756]])

/Users/kylechung/Library/Python/3.6/lib/python/site-packages/sklearn/linear_model/logistic.py:432: FutureWarning:

Default solver will be changed to 'lbfgs' in 0.22. Specify a solver to silence this warning.

2 Automatic Differentiation

In the previous section we implement a simple gradient descent optimizer by manually derive the functional form of gradient on our own. This could be troublesome if our model becomes more and more complicated, as in the case of a deep neural net.

Automatci differentiation is a programming technique to calculate the gradient of any given function. One of the most popular library for this purpose is TensorFlow.

Let’s use tensorflow to implement our simple gradient descent optimizer again. But this time we will NOT explicitly derive the gradient function. Instead, we will only specify the target function which is just the loss function of our model.

/usr/local/lib/python3.6/site-packages/h5py/__init__.py:36: FutureWarning:

Conversion of the second argument of issubdtype from `float` to `np.floating` is deprecated. In future, it will be treated as `np.float64 == np.dtype(float).type`.

WARNING: The TensorFlow contrib module will not be included in TensorFlow 2.0.
For more information, please see:
  * https://github.com/tensorflow/community/blob/master/rfcs/20180907-contrib-sunset.md
  * https://github.com/tensorflow/addons
If you depend on functionality not listed there, please file an issue.

[[6.0113106]
 [3.9624662]]
[[7.1964693]
 [4.8522964]]

In the above coding example one should realize that we no longer need to hardcode the functional form of the gradients. Instead we just plug-in the loss function and let tensorflow to do the gradient calculation for us.

Of course in actual development we will use higher-level APIs to implement our model, where the entire optimization process is abstracted away from the application code.

3 Neural Networks

Both linear regression and logistic regression can be considered as simple additive model of the form:

\[ \hat{y} = \Phi\bigg(\sum_{i=1}^Pw_ix_i\bigg), \]

where \(P\) is the number of features used, \(x_i\) is the \(i\)-th feature, and \(\Phi(\cdot)\) is a function applied to the output. In linear regression \(\Phi(\cdot)\) is simply an identity function. In logistic regression \(\Phi(\cdot)\) is the standard sigmoid function.

Now consider there is a way to ensemble multiple such additive models together to generate a potentially better and more sophisticated model. We use the following diagram for illustration.

Registered S3 methods overwritten by 'ggplot2':
  method         from 
  [.quosures     rlang
  c.quosures     rlang
  print.quosures rlang

In the above diagram, \(Y_{11}\) is a single additive model

\[ Y_{11} = \Phi(W_{111}X_1 + W_{211}X_2 + W_{311}X_3). \]

Similarly \(Y_{12}\) is another such model (with the same input feature set but different model weights)

\[ Y_{12} = \Phi(W_{112}X_1 + W_{212}X_2 + W_{312}X_3). \]

Model \(Y_2\) is yet another additive model but takes the output of the above two models:

\[ Y_2 = \Phi(W_{1121}Y_{11} + W_{1221}Y_{12}). \]

The above setup is a simple architecture of a neural network model, with only one hidden layer of two neurons. (We also ignore the constant/bias term in each layer for simplicity.) A neuron is simply an additive model with a so-called activation function \(\Phi(\cdot)\) to transform the output from any real number into a scaled signal.

One now can easily realize that a logistic regression model could be viewed as a degenerated neural network model with single neuron and using sigmoid as the activation function. And a linear regression model is a degenerated neural network model with single neuron and without an activation function.

3.1 Activation Function

Why do we need the activation function? In the above neural network model in the absence of activation function the final output model \(Y_2\) will degenerate into a simple linear model. We can use simpler notations to demonstrate this:

\[ \begin{aligned} y_1 &= ax + b, \\ y_2 &= cx + d, \\ y_3 &= e + fy_1 + gy_2 \\ &= e + f(ax + b) + g(cx + d) \\ &= \underbrace{(e + fb + gd)}_\text{Bias} + \underbrace{(fa + gc)}_\text{Weight}x. \end{aligned} \]

Without activation function, no matter how many neurons or layers we design for our model, it eventually reduces to a simple linear model. With the activation function applied to each neuron, the model becomes non-linear and hence can handle much more complicated patterns hidden behind the data.

Some popular activation functions:

3.2 Backpropagation

To solve for model weights in a neural network, we use a technique called backpropagation which is essentially an iterative process of gradient descent.

To simplify notation we assume each neuron is simply a univariate model. Consider the following minimum architecture:

Mathematically:

\[ \begin{aligned} \hat{y} &= \Phi(b_1 + w_1z) \\ &= \Phi(b_1 + w_1\Phi(b_0 + w_0x)), \end{aligned} \]

where

\[ z = \Phi(b_0 + w_0x), \]

and

\[ \Phi(t) = \frac{1}{1 + e^{-t}}. \]

3.2.1 MSE Loss

Though it may not be very meaningful to use MSE loss when the output layer is applied with an activation function, we can still do it for educational purpose.

\[ \mbox{MSE-Loss} = \frac{1}{N}\sum_i^N (y_i - \hat{y}_i)^2. \]

Firstly we take the derivative w.r.t. the weight in the last layer:

\[ \begin{aligned} \frac{\partial \mbox{MSE-Loss}}{\partial w_1} &= - \frac{1}{N}\sum_i (y_i - \hat{y}_i)\frac{\partial \hat{y}_i}{\partial w_1} \\ &= - \frac{1}{N}\sum_i (y_i - \hat{y}_i) \underbrace{ \frac{\partial t}{\partial w_1}\frac{\partial \Phi(t)}{\partial t} }_{t = b_1 + w_1\Phi(b_0 + w_0x)}\\ &= - \frac{1}{N}\sum_i (y_i - \hat{y}_i) \cdot \Phi(t)(1 - \Phi(t)) \cdot z_i. \end{aligned} \]

Similarly for the bias in the last layer:

\[ \frac{\partial \mbox{MSE-Loss}}{\partial b_1} = - \frac{1}{N}\sum_i (y_i - \hat{y}_i) \cdot \Phi(t)(1 - \Phi(t)). \]

Now move on to the bias and weight in the first layer:

\[ \begin{aligned} \frac{\partial \mbox{MSE-Loss}}{\partial w_0} &= - \frac{1}{N}\sum_i (y_i - \hat{y}_i)\frac{\partial \hat{y}_i}{\partial w_0} \\ &= - \frac{1}{N}\sum_i (y_i - \hat{y}_i) \underbrace{ \frac{\partial t}{\partial w_0}\frac{\partial \Phi(t)}{\partial t} }_{t = b_1 + w_1\Phi(b_0 + w_0x)}\\ &= - \frac{1}{N}\sum_i (y_i - \hat{y}_i) \cdot \Phi(t)(1 - \Phi(t)) \cdot \underbrace{ \Phi(k)(1 - \Phi(k)) }_{k = b_0 +w_0x} \cdot w_1 \cdot x_i, \\ \frac{\partial \mbox{MSE-Loss}}{\partial b_0} &= - \frac{1}{N}\sum_i (y_i - \hat{y}_i) \cdot \Phi(t)(1 - \Phi(t)) \cdot \Phi(k)(1 - \Phi(k)). \end{aligned} \]

One can clearly see there is a linkage between the derivative of the weights in consecutive layers:

\[ \begin{aligned} \frac{\partial \mbox{MSE-Loss}}{\partial w_1} &= - \frac{1}{N}\sum_i (y_i - \hat{y}_i) \cdot \Phi(t)(1 - \Phi(t)) \cdot z_i, \\ \frac{\partial \mbox{MSE-Loss}}{\partial w_0} &= - \frac{1}{N}\sum_i (y_i - \hat{y}_i) \cdot \underbrace{\Phi(t)(1 - \Phi(t))}_{\hat{y}_i(1 - \hat{y}_i)} \cdot \underbrace{\Phi(k)(1 - \Phi(k)) \cdot w_1 \cdot x_i}_{\frac{\partial w_1z}{\partial w_0} = \frac{\partial w_1\Phi(b0 + w_0x)}{\partial w_0}}. \end{aligned} \]

3.2.2 Cross-Entropy Loss

Similarly we can derive the gradients for cross-entropy loss.

\[ \begin{aligned} \mbox{LogLoss} &= - \frac{1}{N}\sum_i^N \bigg[ y_i\ln\hat{y}_i + (1 - y_i)\ln(1 - \hat{y}_i)\bigg], \\ \frac{\partial \mbox{LogLoss}}{\partial w_1} &= - \frac{1}{N} \sum_i (y_i - \hat{y}_i)z_i, \\ \frac{\partial \mbox{LogLoss}}{\partial w_0} &= - \frac{1}{N} \sum_i (y_i - \hat{y}_i)\Phi(k)(1 - \Phi(k))w_1x_i.\\ \end{aligned} \]

(Skip the bias terms to save space.)

Now let’s implement the simple neural network model in Python:

Here we will use the hello-world example of artificial neural network: The XOR problem. The XOR logical outcome, besides extremely simple, is not linearly separable. So it serves as a good example of showcasing neural networks’ non-linearity.

The input data is simply combination of two binary switches. (For completeness we also include a constant term which always evaluate to 1 as the first feature.) The output data is the XOR result.

[[1 0 0]
 [1 1 0]
 [1 0 1]
 [1 1 1]]
[[0]
 [1]
 [1]
 [0]]

Now let’s see if our simple neural network model can learn the XOR pattern.

'0.016509058781027677,0.9728542987218917,0.9784540441634975,0.027059912943542017'
[[-2.02258664  1.42223805 -1.71522187 -4.26403023]
 [ 6.22204576  5.73421659 -0.35405646  2.29735218]
 [ 5.86924511 -3.55734133  4.32911695  3.3323955 ]]
[[10.56290787]
 [-5.62409836]
 [-4.67738934]
 [-5.56713542]]
'0.0001870860964935529,0.9994879226437576,0.9993958543889606,0.0006300370523400314'

For this simple example, both MSE and cross-entropy loss can work fine to figure out the XOR pattern. (Strictly speaking cross-entropy loss performs better.)

3.3 Regularization

3.3.1 L2-Norm

3.3.2 L1-Norm

3.3.3 Dropout


  1. One can try change the sample size arbitrarily to see the behavior of the estimator.

  2. Here we use the common derivatives: \(\frac{df(x)^n}{dx} = nf(x)^{n-1}f'(x)\) and \(\frac{de^{f(x)}}{dx} = f'(x)e^{f(x)}.\)

  3. Here we use the common derivative \(\frac{d\ln f(x)}{dx} = \frac{f'(x)}{f(x)}\) and the chain rule to handle the term \(\frac{\partial\ln q_i}{\partial\beta_0}\) where \(q_i\) is the sigmoid computed for the \(i\)-th example.

LS0tCnRpdGxlOiAiTmV1cmFsIE5ldHdvcmtzIEZ1bmRhbWVudGFscyIKc3VidGl0bGU6ICJ3aXRoIEV4YW1wbGVzIHVzaW5nIFB5dGhvbiIKYXV0aG9yOgotIG5hbWU6IEt5bGUgQ2h1bmcKICBhZmZpbGlhdGlvbjoKZGF0ZTogImByIGZvcm1hdChTeXMudGltZSgpLCAnJWQgJUIgJVknKWAiCm91dHB1dDoKICBodG1sX25vdGVib29rOiAKICAgIG51bWJlcl9zZWN0aW9uczogeWVzCiAgICB0aGVtZTogZmxhdGx5CiAgICB0b2M6IHllcwogICAgaGlnaGxpZ2h0OiBweWdtZW50cwotLS0KPCEtLSBFbWJlZCBwbG90bHkgamF2YXNjcmlwdCBsaWJyYXJ5LgogIFRoZSBwcmV2aWV3IG9mIHBsb3RseSBvdXRwdXQgaW4gUlN0dWRpbyB3b24ndCB3b3JrCiAgc2luY2Ugd2UgZG9uJ3QgaW5jbHVkZSB0aGUgcGxvdGx5LmpzIGluIGVhY2ggaW5kaXZpZHVhbCBwbG90LgotLT4gCjxzY3JpcHQgc3JjPSJqcy9wbG90bHktbGF0ZXN0Lm1pbi5qcyI+PC9zY3JpcHQ+Cgo8IS0tRm9yIGVxdWF0aW9uIHJlZmVyZW5jZS4tLT4gCjxzY3JpcHQgdHlwZT0idGV4dC94LW1hdGhqYXgtY29uZmlnIj4KTWF0aEpheC5IdWIuQ29uZmlnKHsKICBUZVg6IHsgZXF1YXRpb25OdW1iZXJzOiB7IGF1dG9OdW1iZXI6ICJBTVMiIH0gfQp9KTsKPC9zY3JpcHQ+CgpgYGB7ciBzZXR1cCwgaW5jbHVkZT1GQUxTRX0KbGlicmFyeShyZXRpY3VsYXRlKQp1c2VfcHl0aG9uKFN5cy5nZXRlbnYoIlBZVEhPTl9QQVRIIiksIHJlcXVpcmVkPVRSVUUpCmBgYAoKIyBQcmVyZXF1aXNpdGVzCgpCZWZvcmUgd2UgZXZlbiBzdGFydCwKaXQgaXMgb2YgY3J1Y2lhbCBpbXBvcnRhbmNlIHRvIGZpcnN0IHVuZGVyc3RhbmQgZGVlcGx5IGxpbmVhciBhbmQgbG9naXN0aWMgcmVncmVzc2lvbi4KVGhpcyBpcyBiZWNhdXNlIChhcyB3ZSB3aWxsIHNlZSBpbiBsYXRlciBkaXNjdXNzaW9uKSB0aGV5IGFyZSB0aGUgdmVyeSBiYXNpYyBjb21wb25lbnRzIGluIGEgZ2VuZXJhbCBuZXVyYWwgbmV0d29yayBtb2RlbC4KCiMjIExpbmVhciBSZWdyZXNzaW9uCgpBIGxpbmVhciBtb2RlbCBjYW4gYmUgd3JpdHRlbiBpbiBhIG1hdHJpeCBmb3JtCgokJApZID0gWFxiZXRhICsgXGVwc2lsb24sCiQkCndoZXJlICRZJCBpcyB0aGUgb3V0cHV0IG9yIGxhYmVsIHZlY3RvciBvZiBsZW5ndGggJE4kIChudW1iZXIgb2Ygb2JzZXJ2YXRpb25zKSwKJFgkIGlzIHRoZSBpbnB1dCBmZWF0dXJlIG1hdHJpeCAocmVmZXJyZWQgdG8gYXMgdGhlICpkZXNpZ24gbWF0cml4KiBpbiBzdGF0aXN0aWNzKSB3aXRoIGRpbWVuc2lvbiAkTiQgYnkgJFAkIChudW1iZXIgb2YgZmVhdHVyZXMpLAokXGJldGEkIGlzIHRoZSBtb2RlbCB3ZWlnaHRzL2NvZWZmaWNpZW50cyAoYSBjb2x1bW4gdmVjdG9yIG9mIGxlbmd0aCAkUCQpIGZvciB3aGljaCB3ZSdkIGxpa2UgdG8gc29sdmUsCiRcZXBzaWxvbiQgaXMgdGhlIG1vZGVsIHJlc2lkdWFsIG9yIGVycm9yIHZlY3Rvci4KCiMjIyBPcmRpbmFyeSBMZWFzdCBTcXVhcmVzCgpUaGUgY2xhc3NpY2FsIHdheSB0byBzb2x2ZSBmb3IgJFxiZXRhJCBpcyBbb3JkaW5hcnkgbGVhc3Qgc3F1YXJlc10oaHR0cHM6Ly9lbi53aWtpcGVkaWEub3JnL3dpa2kvT3JkaW5hcnlfbGVhc3Rfc3F1YXJlcykuClRoZSBpZGVhIG9mIE9MUyBpcyBmaW5kIG91dCB0aGUgd2VpZ2h0cyB0aGF0IG1pbmltaXplIHRoZSBtZWFuIG9mIHNxdWFyZWQgbW9kZWwgZXJyb3JzOgoKJCQKXGJlZ2lue2FsaWduZWR9ClxtYm94e21zZSAobG9zcyl9CiY9IFxmcmFjezF9e059XHN1bV9pXGVwc2lsb25eMl9pIFxcCiY9IFxmcmFjezF9e059XHN1bV9pKHlfaSAtIFxiZXRhIHhfaSleMiwKXGVuZHthbGlnbmVkfQokJAoKd2hlcmUgJHlfaSQgYW5kICR4X2kkIGlzIHRoZSAkaSQtdGggb2JzZXJ2YXRpb24uClRoZSBmaXJzdC1vcmRlciBjb25kaXRpb24gKHJlcXVpcmluZyB0aGF0IHRoZSBmaXJzdC1vcmRlciBkZXJpdmF0aXZlIHcuci50LiB3ZWlnaHRzIGFyZSB6ZXJvKSBnaXZlcyB1cyB0aGUgT0xTIHNvbHV0aW9uIGZvciBtb2RlbCB3ZWlnaHRzICRcYmV0YSQgYW5hbHl0aWNhbGx5IChpbiBtYXRyaXggbm90YXRpb24pOgoKJCQKXGJlZ2lue2VxdWF0aW9ufSBcbGFiZWx7ZXE6b2xzfQpcaGF0e1xiZXRhfSA9IChYJ1gpXnstMX1YJ1kuClxlbmR7ZXF1YXRpb259CiQkCgpgYGB7cHl0aG9uIGxpbmVhcl9yZWdfb2xzfQppbXBvcnQgbnVtcHkgYXMgbnAKZnJvbSBudW1weS5saW5hbGcgaW1wb3J0IGludgoKZGVmIG9scyhYLCB5KToKICAgIHJldHVybiBpbnYoWC5ULmRvdChYKSkuZG90KFguVCkuZG90KHkpCmBgYAoKTGV0J3MgY29uc2lkZXIgYSB0b3kgbW9kZWwgd2l0aCBvbmx5IG9uZSBub24tY29uc3RhbnQgZmVhdHVyZToKCiQkCnlfaSA9IDYgKyA0eF9pICsgXGVwc2lsb25faS4KJCQKCkluIHRoaXMgbW9kZWwgdGhlIG91dGNvbWUgJHkkIGlzIGRldGVybWluZWQgYnkgYSBiaWFzIHRlcm0gcGx1cyBhIHNpbmdsZSB2YXJpYWJsZSAkeCQsCndpdGggYW4gaW5kZXBlbmRlbnRseSBkaXN0cmlidXRlZCBub2lzZSB0ZXJtICRcZXBzaWxvbiBcc2ltIFxtYm94e05vcm1hbH0oMCwgMSkkLgoKQ3JlYXRlIHNvbWUgcmFuZG9tIGRhdGEgZ2VuZXJhdGVkIGZyb20gdGhpcyBtb2RlbDoKCmBgYHtweXRob24gbGluZWFyX3JlZ190b3lfZXhhbXBsZX0KIyBDcmVhdGUgdG95IGV4YW1wbGUuCm5wLnJhbmRvbS5zZWVkKDc3NykKCk4gPSAxMDAwClggPSBucC5zdGFjayhbbnAub25lcyhOKSwgbnAucmFuZG9tLm5vcm1hbChzaXplPU4pXSwgYXhpcz0xKQpiZXRhID0gbnAuYXJyYXkoWzYsIDRdLCBkdHlwZT1ucC5mbG9hdDMyKSAgIyBUcnVlIG1vZGVsIHdlaWdodHMuCmUgPSBucC5yYW5kb20ubm9ybWFsKHNpemU9TikKeSA9IFguZG90KGJldGEpICsgZQoKcHJpbnQoWFs6MTBdKQpgYGAKCmBgYHtweXRob24gbGluZWFyX3JlZ19wbG90fQpmcm9tIHBsb3RseS5vZmZsaW5lIGltcG9ydCBwbG90CmltcG9ydCBwbG90bHkuZ3JhcGhfb2JqcyBhcyBnbwoKZGVmIHBsb3Rfb2ZmbGluZShkYXRhLCBsYXlvdXQsIG9maWxlKToKICBwID0gcGxvdCh7ImRhdGEiOiBkYXRhLCAibGF5b3V0IjogbGF5b3V0fSwKICAgICAgICAgICBmaWxlbmFtZT1vZmlsZSwgYXV0b19vcGVuPUZhbHNlLCBpbmNsdWRlX3Bsb3RseWpzPUZhbHNlKQogIHJldHVybiBwCgpvZmlsZSA9ICJwbG90cy90b3lfcmVnLmh0bWwiCnAgPSBwbG90X29mZmxpbmUoCiAgb2ZpbGU9b2ZpbGUsCiAgZGF0YT1bZ28uU2NhdHRlcih4PVhbOiwxXSwgeT15LCBtb2RlPSJtYXJrZXJzIildLAogIGxheW91dD1nby5MYXlvdXQodGl0bGU9IkRhdGEgR2VuZXJhdGVkIGZyb20gVG95IE1vZGVsIiwKICAgICAgICAgICAgICAgICAgIHhheGlzPWRpY3QodGl0bGU9IngiKSwKICAgICAgICAgICAgICAgICAgIHlheGlzPWRpY3QodGl0bGU9InkiKSkpCmBgYAoKYGBge3IsIGVjaG89RkFMU0V9Cmh0bWx0b29sczo6aW5jbHVkZUhUTUwocHkkb2ZpbGUpCmBgYAoKV2l0aG91dCBjb25zaWRlcmF0aW9uIG9mIHRoZSBub2lzZSB0ZXJtLAp0aGUgT0xTIGVzdGltYXRvciB3aWxsIHNvbHZlIHByZWNpc2VseSBmb3IgdGhlIHRydWUgbW9kZWwgd2VpZ2h0czoKCmBgYHtweXRob24gbGluZWFyX3JlZ19vbHNfZGV0ZXJtaW5pc3RpY30KcHJpbnQob2xzKFgsIHkgLSBlKSkKYGBgCgpPZiBjb3Vyc2UgaW4gdGhlIHJlYWwgd29ybGQgdGhlIG5vaXNlIHRlcm0gY2Fubm90IGJlIGRldGVybWluZWQgYW5kIHVzdWFsbHkgdGhlIGZlYXR1cmUgYWxvbmUgY2Fubm90IGV4cGxhaW4gZW50aXJlbHkgdGhlIHZhcmlhdGlvbiBpbiB0aGUgb3V0Y29tZS4KVGhpcyBtZWFucyB0aGF0IHdoYXQgd2UgYWN0dWFsbHkgZXN0aW1hdGUgd2lsbCBiZSB0aGUgZXhwZWN0ZWQgdmFsdWUgb2YgbW9kZWwgd2VpZ2h0czoKCmBgYHtweXRob24gbGluZWFyX3JlZ19vbHNfd2l0aF9lcHNpbG9ufQpwcmludChvbHMoWCwgeSkpCmBgYAoKQnkgdGhlIFtMYXcgb2YgTGFyZ2UgTnVtYmVyXShodHRwczovL2VuLndpa2lwZWRpYS5vcmcvd2lraS9MYXdfb2ZfbGFyZ2VfbnVtYmVycykgYW5kIFtDZW50cmFsIExpbWl0IFRoZW9yZW1dKGh0dHBzOi8vZW4ud2lraXBlZGlhLm9yZy93aWtpL0NlbnRyYWxfbGltaXRfdGhlb3JlbSksCnRoZSBPTFMgZXN0aW1hdG9yIHdpbGwgY29udmVyZ2UgaW4gcHJvYmFiaWxpdHkgdG8gdGhlIHRydWUgbW9kZWwgd2VpZ2h0cyBhbmQgZGlzdHJpYnV0ZWQgYXN5bXB0b3RpY2FsbHkgTm9ybWFsIGluIGxhcmdlIHNhbXBsZS5eW09uZSBjYW4gdHJ5IGNoYW5nZSB0aGUgc2FtcGxlIHNpemUgYXJiaXRyYXJpbHkgdG8gc2VlIHRoZSBiZWhhdmlvciBvZiB0aGUgZXN0aW1hdG9yLl0KClRoZSBpc3N1ZSBvZiB0aGUgYWJvdmUgYXBwcm9hY2ggaXMgdGhhdCBlcXVhdGlvbiAkXGVxcmVme2VxOm9sc30kIGlzIG5vdCBudW1lcmljYWxseSBzdGFibGUgd2hlbiBpdCBjb21lcyB0byBsYXJnZS1zY2FsZSBhcHBsaWNhdGlvbiB3aGVyZSB3ZSBtYXkgaGF2ZSBsb3RzIG9mIG9ic2VydmF0aW9ucyBhbmQgbG90cyBvZiBmZWF0dXJlcy4KT25lIHZlcnkgdXNlZnVsIHNvbHV0aW9uIHRvIHNvbHZlIHRoZSBlc3RpbWF0b3IgbnVtZXJpY2FsbHkgaW4gbGFyZ2Utc2NhbGUgYXBwbGljYXRpb24gaXMgdGhlICpncmFkaWVudCBkZXNjZW50KiBhcHByb2FjaC4KCiMjIyBHcmFkaWVudCBEZXNjZW50IHdpdGggTWVhbiBTcXVhcmVkIEVycm9yCgpJbnN0ZWFkIG9mIHNvbHZpbmcgdGhlIGZpcnN0LW9yZGVyIGNvbmRpdGlvbiBhbmFseXRpY2FsbHksCndlIGNhbiBkbyBpdCBudW1lcmljYWxseS4KR3JhZGllbnQgZGVzY2VudCBpcyBhIDFzdC1vcmRlciBvcHRpbWl6YXRpb24gdGVjaG5pcXVlIHRvIGZpbmQgbG9jYWwgb3B0aW11bSBvZiBhIGdpdmVuIGZ1bmN0aW9uLgoKSW4gdGhlIG1vZGVsIHRyYWluaW5nIGV4ZXJjaXNlIG91ciB0YXJnZXQgZnVuY3Rpb24gaXMgdGhlIGxvc3Mgc28gdGhlIG9wdGltaXphdGlvbiBwcm9ibGVtIGlzOgoKJCQKXG9wZXJhdG9ybmFtZSp7YXJnbWlufV9cYmV0YSBcbWJveHtMb3NzfSA9IFxmcmFjezF9e059XHN1bV9pKHlfaSAtIFxiZXRhIHhfaSleMi4KJCQKClRoYXQgaXMsCndlJ2QgbGlrZSB0byBmaWd1cmUgb3V0IG1vZGVsIHdlaWdodHMgdGhhdCBtaW5pbWl6ZSB0aGUgbG9zcyB3aGljaCBpcyBkZWZpbmVkIGJ5IHRoZSBtZWFuIHNxdWFyZWQgZXJyb3JzIHdoZW4gdGhlIG1vZGVsIGlzIGEgcmVncmVzc2lvbiBtb2RlbC4KClRoZSBpZGVhIG9mIGdyYWRpZW50IGRlc2NlbnQgaXMgdG8KCjEuIERlcml2ZSB0aGUgZnVuY3Rpb25hbCBmb3JtIG9mIHRoZSBncmFkaWVudCBvZiBsb3NzIHcuci50LiB0byBhbGwgd2VpZ2h0cwoyLiBJbml0aWFsaXplIGFsbCBtb2RlbCB3ZWlnaHRzIHJhbmRvbWx5CjMuIENhbGN1bGF0ZSB0aGUgZ3JhZGllbnQgdmFsdWUgdXNpbmcgdGhlIGFjdHVhbCBkYXRhIGFuZCB0aGUgY3VycmVudCB2YWx1ZSBvZiB3ZWlnaHRzCjQuIFVwZGF0ZSB0aGUgd2VpZ2h0cyBieSAocGFydGlhbGx5KSB0aGUgYW1vdW50IG9mIGdyYWRpZW50IGp1c3QgY2FsY3VsYXRlZAo1LiBSZXBlYXQgMyBhbmQgNCB1bnRpbCB0aGUgcmVzdWx0aW5nIGdyYWRpZW50cyBiZWNvbWUgc21hbGwgZW5vdWdoCgpMZXQncyB1c2UgdGhlIHRveSBleGFtcGxlIHRvIGFjdHVhbGx5IGltcGxlbWVudCBhIGdyYWRlbnQgZGVzY2VudCBvcHRpbWl6ZXIgZnJvbSBzY3JhdGNoLgpGaXJzdCB3ZSByZS13cml0ZSB0aGUgbG9zcyBmdW5jdGlvbiBleHBsaWNpdGx5IHdpdGggb3VyIHNldHVwIG9mIG9uZSBjb2VmZmljaWVudCB3aXRoIGEgY29uc3RhbnQgKCRcYmV0YSA9IFtcYmV0YV8wLCBcYmV0YV8xXSQpOgoKJCQKXG1ib3h7TG9zc30gPSBcZnJhY3sxfXtOfVxzdW1faVxiaWdbeV9pLShcYmV0YV8wICsgXGJldGFfMXhfaSlcYmlnXV4yLgokJAoKTm93IHRoZSBncmFkaWVudCAob3IgZXF1aXZhbGVudGx5IHRoZSAxc3Qtb3JkZXIgZGVyaXZhdGl2ZSkgdy5yLnQuIHRvIHdlaWdodHMgd2lsbCBiZToKCiQkClxiZWdpbnthbGlnbmVkfQpcZnJhY3tccGFydGlhbFxtYm94e0xvc3N9fXtccGFydGlhbFxiZXRhXzB9IAomPSAtIFxmcmFjezJ9e059XHN1bV9pIFxiaWdbIHlfaSAtIChcYmV0YV8wICsgXGJldGFfMXhfaSkgXGJpZ10sIFxcClxmcmFje1xwYXJ0aWFsXG1ib3h7TG9zc319e1xwYXJ0aWFsXGJldGFfMX0gCiY9IC0gXGZyYWN7Mn17Tn1cc3VtX2kgXGJpZ1sgeV9pIC0gKFxiZXRhXzAgKyBcYmV0YV8xeF9pKSBcYmlnXXhfaS4KXGVuZHthbGlnbmVkfQokJAoKVGhlIGNvcnJlc3BvbmRpbmcgcHl0aG9uIGZ1bmN0aW9uIGNhbiBiZSBjb2RlZCBhczoKCmBgYHtweXRob24gbGluZWFyX3JlZ19ncmFkX2Z1bmN9CmRlZiBncmFkX2Z1bmMoWCwgeSwgYmV0YSk6CiAgIiIiQ2FsY3VsYXRlIHZlY3Rvcml6ZWQgZ3JhZGllbnRzLiIiIgogIHJldHVybiAtMiAqICgoeSAtIFguZG90KGJldGEpKS5kb3QoWCkpIC8gWC5zaGFwZVswXQpgYGAKCklmIHdlIHNldCB0aGUgYWJvdmUgZXF1YXRpb25zIHRvIHplcm8gd2UgY2FuIHNvbHZlIGZvciAkXGJldGFfMCQgYW5kICRcYmV0YV8xJCBhbmFseXRpY2FsbHkgYW5kIHRoZSBzb2x1dGlvbiB3aWxsIGJlIGV4YWN0bHkganVzdCBlcXVhdGlvbiAkXGVxcmVme2VxOm9sc30kLgpCdXQgYXMgd2UganVzdCBwb2ludGVkIG91dCBpdCBzdWZmZXJzIGZyb20gbnVtZXJpY2FsIHN0YWJpbGl0eSBpc3N1ZS4KClRoZSBtaW5pbXVtIGltcGxlbWVudGF0aW9uIG9mIG91ciBncmFkaWVudCBkZXNjZW50IG9wdGltaXplciBpcyBqdXN0IGEgZmV3IGxpbmVzOgoKYGBge3B5dGhvbiBsaW5lYXJfcmVnX2dkfQpkZWYgZ2Rfb3B0aW1pemUoWCwgeSwgbHI9LjAxLCBuX3N0ZXA9MTAwKToKICBiID0gbnAucmFuZG9tLm5vcm1hbChzaXplPVguc2hhcGVbMV0pCiAgZm9yIHN0ZXAgaW4gcmFuZ2Uobl9zdGVwKToKICAgIGIgLT0gbHIqZ3JhZF9mdW5jKFgsIHksIGIpCiAgcmV0dXJuIGIKCnByaW50KGdkX29wdGltaXplKFgsIHksIG5fc3RlcD0zMDAwKSkKYGBgCgpBcyB3ZSBjYW4gc2VlIHRoZSByZXN1bHQgaXMgdmVyeSBjbG9zZWQgdG8gb3VyIGFuYWx5dGljYWwgc29sdXRpb24uCgojIyMjIE9uIExlYXJuaW5nIFJhdGUgey19CgpMZWFybmluZyByYXRlIGlzIGEgaHlwZXItcGFyYW1ldGVyIGZvciBncmFkaWVudCBkZXNjZW50IG9wdGltaXplci4KVGhlIGdyYWRpZW50IHVwZGF0ZSB0byBvdXIgbW9kZWwgd2VpZ2h0cyBpcyBzY2FsZWQgZG93biBieSB0aGUgbGVhcm5pbmcgcmF0ZSB0byBtYWtlIHN1cmUgY29udmVyZ2VuY2UuClRvbyBsYXJnZSB0aGUgbGVhcm5pbmcgcmF0ZSB3aWxsIGV4cGxvZGUgdGhlIGdyYWRpZW50LgpUb28gc21hbGwgdGhlIGxlYXJuaW5nIHJhdGUgd2lsbCBzbG93IGRvd24gdGhlIGNvbnZlcmdlbmNlIGFuZCBzb21ldGltZXMgcmVzdWx0IGluIHRoZSBvcHRpbWl6ZXIgdHJhcHBlZCBhdCBsb2NhbCBzdWItb3B0aW11bS4KCkxldCdzIHJlLXdyaXRlIG91ciBncmFkaWVudCBkZXNjZW50IG9wdGltaXplciB0byBhbHNvIHRyYWNrIHRoZSBsb3NzIGZyb20gZWFjaCB0cmFpbmluZyBzdGVwLgpBbmQgd2UgdXNlIHRoZSBzYW1lIGluaXRpYWxpemF0aW9uIGZvciBhIGZhaXIgY29tcGFyaXNvbi4KCmBgYHtweXRob24gbGluZWFyX3JlZ19nZF93aXRoX2xvc3N9CmRlZiBsb3NzKFgsIHksIGJldGEpOgogIHJldHVybiAoKFguZG90KGJldGEpIC0geSkqKjIpLm1lYW4oKQoKZGVmIGdkX29wdGltaXplKFgsIHksIGxyPS4wMSwgbl9zdGVwPTEwMCk6CiAgYiA9IG5wLmFycmF5KFswLjAsIDAuMF0pCiAgbCA9IFtsb3NzKFgsIHksIGIpXQogIGZvciBzdGVwIGluIHJhbmdlKG5fc3RlcCk6CiAgICBiIC09IGxyKmdyYWRfZnVuYyhYLCB5LCBiKQogICAgbC5hcHBlbmQobG9zcyhYLCB5LCBiKSkKICByZXR1cm4gYiwgbApgYGAKCk5vdyB3ZSBydW4gdGhlIG9wdGltaXphdGlvbiB3aXRoIGEgdmFyaWV0eSBvZiBkaWZmZXJlbnQgbGVhcm5pbmcgcmF0ZXMuCkZvciBpbGx1c3RyYXRpb24gcHVycG9zZSB3ZSB3aWxsIG9ubHkgcnVuIGEgZmV3IHN0ZXBzLgoKYGBge3B5dGhvbiBsaW5lYXJfcmVnX2RpZmZfbHJ9CmJldGFzID0ge30KbG9zc2VzID0ge30KZm9yIGxyIGluIFsuMDAxLCAuMDEsIC4wNSwgLjEsIDFdOgogIGJldGFzW2xyXSwgbG9zc2VzW2xyXSA9IGdkX29wdGltaXplKFgsIHksIGxyPWxyLCBuX3N0ZXA9MTUpCgpmb3IgciwgYiBpbiBiZXRhcy5pdGVtcygpOgogIHByaW50KCJMZWFybmluZyBSYXRlIHs6NX0gfCBFc3RpbWF0ZToge30iLmZvcm1hdChyLCBiKSkKYGBgCgpUaGUgcmVzdWx0IHN1Z2dlc3RzIHRoYXQgYSBsZWFybmluZyByYXRlIG9mIDEgaXMgdG9vIGxhcmdlIGZvciBvdXIgcHJvYmxlbS4KVGhlIGdyYWRpZW50IGV4cGxvZGVzIHdoaWNoIG1ha2Ugb3VyIHNvbHV0aW9uIGRpdmVyZ2UuCkFuZCBhIGxvd2VyIGxlYXJuaW5nIHJhdGUgaW4gZ2VuZXJhbCBjb252ZXJnZXMgc2xvd2VyIHRvIHRoZSBvcHRpbXVtLgpOdW1iZXIgb2YgZXhhbXBsZXMgdXNlZCB0byBjYWxjdWxhdGUgdGhlIGdyYWRpZW50IGFsc28gd2lsbCBhZmZlY3QgdGhlIGNvbnZlcmdlbmNlIGJlaGF2aW9yLgpJbiBnZW5lcmFsIGlmIHRoZSBzYW1wbGUgc2l6ZSBpcyB0b28gc21hbGwgYSBzbWFsbGVyIGxlYXJuaW5nIHJhdGUgc2hvdWxkIGJlIHVzZWQgdG8gYXZvaWQgZ3JhZGllbnQgZXhwbG9zaW9uLgoKVGhpcyBjYW4gYmUgbW9yZSBjbGVhcmx5IHNlZW4gaWYgd2UgcGxvdCB0aGUgdHJhY2Ugb2Ygb3VyIHRyYWluaW5nIGxvc3NlczoKCmBgYHtweXRob24gbGluZWFyX3JlZ19kaWZmX2xyX3Bsb3R9Cm9maWxlID0gInBsb3RzL3RveV9yZWdfbG9zc19jb21wYXJlLmh0bWwiCnBkYXRhID0gW2dvLlNjYXR0ZXIoeD1ucC5hcmFuZ2UobGVuKGxvc3Nlc1tscl0pKSwgeT1sb3NzZXNbbHJdLCBuYW1lPWxyKSAKICAgICAgICAgZm9yIGxyIGluIGxvc3Nlcy5rZXlzKCldCnAgPSBwbG90X29mZmxpbmUoCiAgb2ZpbGU9b2ZpbGUsCiAgZGF0YT1wZGF0YSwKICBsYXlvdXQ9Z28uTGF5b3V0KAogICAgdGl0bGU9IlRyYWNlIG9mIFRyYWluaW5nIExvc3Mgd2l0aCBWYXJpb3VzIExlYXJuaW5nIFJhdGVzIiwKICAgIHhheGlzPWRpY3QodGl0bGU9IlN0ZXAiKSwKICAgIHlheGlzPWRpY3QodGl0bGU9Ikxvc3MiKSkpCmBgYAoKYGBge3IsIGVjaG89RkFMU0V9Cmh0bWx0b29sczo6aW5jbHVkZUhUTUwocHkkb2ZpbGUpCmBgYAoKSWYgdGhlIGxvc3MgZG9lc24ndCBkZWNyZWFzZSBvdmVyIHRyYWluaW5nIGl0ZXJhdGlvbiwKaXQgaXMgYSBzaWduYWwgdGhhdCBzb21ldGhpbmcgaXMgd3Jvbmcgd2l0aCBvdXIgbW9kZWwuCgpVbmxpa2Ugb3VyIHRveSBpbXBsZW1lbnRhdGlvbiwKaW4gbW9kZXJuIGltcGxlbWVudGF0aW9uIG9mIGFueSBudW1lcmljYWwgb3B0aW1pemVyIHRoZXJlIHdpbGwgYmUgYSBsb3Qgb2YgdGVjaG5pcXVlcyB0byBkbyB0aGUgYmVzdCB0byBhdm9pZCBjb252ZXJnZW5jZSBmYWlsdXJlLgpCdXQgaXQgaXMgdGhlIG1vZGVsIGRldmVsb3BlcidzIHJlc3BvbnNpYmlsaXR5IHRvIGRpYWdub3NlIHRoZSB0cmFpbmluZyBiZWhhdmlvciBiZWZvcmUgYW55dGhpbmcgaXMgZGVsaXZlcmVkIHRvIHRoZSBzdGFrZWhvbGRlci4KQ2hlY2tpbmcgdGhlIGR5bmFtaWNzIG9mIGxvc3MgaXMgdXN1YWxseSB0aGUgZmlyc3QgYW5kIHF1aWNrIHN0ZXAgdG8gZXhhbWluZSB3aGV0aGVyIHRoZSB0cmFpbmluZyB0YXNrIGlzIGZ1bmN0aW9uaW5nIGFzIGV4cGVjdGVkLgoKIyMjIyBCYXRjaCBHcmFkaWVudCBEZXNjZW50IHstfQoKVGhlIHZhbmlsbGEgZ3JhZGllbnQgZGVzY2VudCBvcHRpbWl6ZXIgd2UganVzdCBpbXBsZW1lbnRlZCBoYXMgb25lIGlzc3VlLgpTaW5jZSBmb3IgZWFjaCB1cGRhdGUgaXQgbmVlZHMgdG8gdHJhdmVyc2Ugb3ZlciB0aGUgZW50aXJlIGRhdGFzZXQsCml0IGJlY29tZXMgdG9vIHNsb3cgd2hlbiBpdCBjb21lcyB0byBsYXJnZSBkYXRhc2V0LgoKQmF0Y2ggZ3JhZGllbnQgZGVzY2VudCBpcyB0b28gb3ZlcmNvbWUgdGhpcyBpc3N1ZS4KSW5zdGVhZCBvZiBjYWxjdWxhdGUgdGhlIGdyYWRpZW50IHVzaW5nIHRoZSBlbnRpcmUgZGF0YXNldCwKd2UgY2FuIHVzZSBvbmx5IGEgcmFuZG9tIHN1YnNldCBvZiBpdC4KSXQgd2lsbCBiZSBsZXNzIHByZWNpc2UgYnV0IHN0YXRpc3RpY2FsbHkgdGhlIHJlc3VsdCB3aWxsIGJlIGNvbnNpc3RlbnQuCgpMZXQncyBpbXBsZW1lbnQgYSBiYXRjaCBncmFkaWVudCBkZXNjZW50IG9wdGltaXplcjoKCmBgYHtweXRob24gbGluZWFyX3JlZ19nZF9iYXRjaH0KZGVmIGdkX2JhdGNoX29wdGltaXplKFgsIHksIGxyPS4wMSwgbl9zdGVwPTEwMCwgYmF0Y2hfc2l6ZT02NCk6CiAgYiA9IG5wLnJhbmRvbS5ub3JtYWwoc2l6ZT1YLnNoYXBlWzFdKQogIGwgPSBbbG9zcyhYLCB5LCBiKV0KICBmb3Igc3RlcCBpbiByYW5nZShuX3N0ZXApOgogICAgc2lkID0gbnAucmFuZG9tLnJhbmRpbnQoWC5zaGFwZVswXSwgc2l6ZT1iYXRjaF9zaXplKQogICAgWGIgPSBYW3NpZCw6XQogICAgeWIgPSB5W3NpZF0KICAgIGIgLT0gbHIqZ3JhZF9mdW5jKFhiLCB5YiwgYikKICAgIGwuYXBwZW5kKGxvc3MoWGIsIHliLCBiKSkKICByZXR1cm4gYiwgbAoKYmF0Y2hfYmV0YSwgYmF0Y2hfbG9zcyA9IGdkX2JhdGNoX29wdGltaXplKFgsIHksIG5fc3RlcD0zMDAwLCBiYXRjaF9zaXplPTY0KQpwcmludChiYXRjaF9iZXRhKQpgYGAKCkJhdGNoIG9wdGltaXplciBpcyBjdXJyZW50bHkgdGhlIGJlc3QgcHJhY3RpY2Ugb2YgdHJhaW5pbmcgbmV1cmFsIG5ldHdvcmtzIGluIGxhcmdlIHNjYWxlIGFwcGxpY2F0aW9uLgpUaGUgYmF0Y2ggc2l6ZSBkZXBlbmRzIG9uIHRoZSBhY3R1YWwgYXBwbGljYXRpb24gYnV0IHVzdWFsbHkgcmFuZ2VzIGZyb20gOCB0byAxMDI0LgoKIyMjIyBTdG9jYWhzdGljIEdyYWRpZW50IERlc2NlbnQgey19CgpJZiB3ZSBzZXQgdGhlIGJhdGNoIHNpemUgYXMgZXhhY3RseSAxLAppLmUuLAp0byBjYWxjdWxhdGUgdGhlIGdyYWRpZW50IHVwZGF0ZSBvbmx5IHVzZSBvbmUgZGF0YSBvYnNlcnZhdGlvbiBhdCBhIHRpbWUsCnRoaXMgaXMgcmVmZXJyZWQgdG8gYXMgc3RvY2hhc3RpYyBncmFkaWVudCBkZXNjZW50LgoKSGVyZSB3ZSBpbnRyb2R1Y2UgdGhlIHRlcm0gKmVwb2NoKjoKT25lIGVwb2NoIGlzIGZvciB0aGUgb3B0aW1pemVyIHRvIHRyYXZlcnNlIHRoZSBlbnRpcmUgZGF0YXNldCBvbmNlIChubyBtYXR0ZXIgaG93IG1hbnkgZXhhbXBsZXMgYXJlIHVzZWQgdG8gY2FsY3VsYXRlIHRoZSBncmFkaWVudCBpbiBlYWNoIHVwZGF0ZSkuCk51bWJlciBvZiBlcG9jaHMgY2FuIGJlIGNvbnNpZGVyZWQgYXMgYW5vdGhlciBoeXBlci1wYXJhbWV0ZXIgb2YgYSBtb2RlbC4KV2UgY2FuIGFsc28gaW1wbGVtZW50IGVwb2NoIGluIG91ciBwcmV2aW91cyBiYXRjaCBncmFkaWVudCBkZXNjZW50IG9wdGltaXplciBidXQgZm9yIHNpbXBsaWNpdHkgd2UgaWdub3JlIHRoYXQuCkxldCdzIGltcGxlbWVudCBpdCBpbiBvdXIgU0dEIG9wdGltaXplcjoKCmBgYHtweXRob24gbGluZWFyX3JlZ19zZ2R9CmRlZiBzZ2Rfb3B0aW1pemUoWCwgeSwgbHI9LjAxLCBuX2Vwb2NoPTEwMCk6CiAgYiA9IG5wLnJhbmRvbS5ub3JtYWwoc2l6ZT1YLnNoYXBlWzFdKQogIGwgPSBbbG9zcyhYLCB5LCBiKV0KICBmb3IgZXBvY2ggaW4gcmFuZ2Uobl9lcG9jaCk6CiAgICBzaWQgPSBucC5yYW5kb20ucGVybXV0YXRpb24oWC5zaGFwZVswXSkKICAgIGZvciBpIGluIHNpZDoKICAgICAgYiAtPSBscipncmFkX2Z1bmMoWFtOb25lLGksOl0sIHlbaV0sIGIpCiAgICAgIGwuYXBwZW5kKGxvc3MoWFtOb25lLGksOl0sIHlbaV0sIGIpKQogIHJldHVybiBiLCBsCgpzZ2RfYmV0YSwgc2dkX2xvc3MgPSBzZ2Rfb3B0aW1pemUoWCwgeSwgbHI9LjAxLCBuX2Vwb2NoPTEwKQpwcmludChzZ2RfYmV0YSkKYGBgCgpQbG90IHRoZSBsb3NzZXMgZm9yIHRoZSBmaXJzdCA1MDAgdXBkYXRlcy4KCmBgYHtweXRob24gbGluZWFyX3JlZ19zZ2RfcGxvdH0Kb2ZpbGUgPSAicGxvdHMvdG95X3JlZ19zZ2RfbG9zcy5odG1sIgpwID0gcGxvdF9vZmZsaW5lKAogIG9maWxlPW9maWxlLAogIGRhdGE9W2dvLlNjYXR0ZXIoeD1ucC5hcmFuZ2UobGVuKHNnZF9sb3NzWzo1MDBdKSksIHk9c2dkX2xvc3NbOjUwMF0pXSwKICBsYXlvdXQ9Z28uTGF5b3V0KAogICAgdGl0bGU9IlRyYWNlIG9mIFNHRCBUcmFpbmluZyBMb3NzIiwKICAgIHhheGlzPWRpY3QodGl0bGU9IlN0ZXAiKSwKICAgIHlheGlzPWRpY3QodGl0bGU9Ikxvc3MiKSkpCmBgYAoKYGBge3IsIGVjaG89RkFMU0V9Cmh0bWx0b29sczo6aW5jbHVkZUhUTUwocHkkb2ZpbGUpCmBgYAoKVW5saWtlIHRoZSB2YW5pbGxhIGdyYWRpZW50IGRlc2NlbnQsCnN0b2NoYXN0aWMgZ3JhZGllbnQgZGVzY2VudCBkb2Vzbid0IGVuc3VyZSB0aGUgbG9zcyBpcyBhbHdheXMgZGVjcmVhc2luZy4KQnV0IHN0YXRpc3RpYWNsbHkgaXQgc2hvdWxkIGNvbnZlcmdlIHRvIHRoZSBzYW1lIHNvbHV0aW9uIGFzIHRoZSB2YW5pbGxhIGFwcHJvYWNoLgoKIyMgTG9naXN0aWMgUmVncmVzc2lvbgoKQSBsb2dpc3RpYyByZWdyZXNzaW9uIG1vZGVscyB0aGUgb3V0Y29tZSBwcm9iYWJsaXN0aWNhbGx5OgoKJCQKXGJlZ2lue2VxdWF0aW9ufSBcbGFiZWx7ZXE6bG9naXR9ClAoWSA9IDEpID0gXGZyYWN7MX17MSArIGVeey1YXGJldGF9fSwKXGVuZHtlcXVhdGlvbn0KJCQKCkhlcmUgdGhlIHNpZ21vaWQgZnVuY3Rpb24gJHModCkgPSBcZnJhY3sxfXsxICsgZV57LXR9fSQgaXMgdXNlZCB0byB0cmFuc2Zvcm0gYSByZWFsIG51bWJlciBpbnRvIHByb2JhYmlsaXR5IHNwYWNlICRbMCwgMV0kLgoKV2UgY2FuIGludGVycHJldCB0aGUgbW9kZWwgYXMgYSBsaW5lYXIgbW9kZWwgaW4gbG9nLW9kZHMuCkFzc3VtaW5nIFkgaXMgYmluYXJ5IGFuZCB0YWtlIGEgdmFsdWUgb2YgMCBvciAxLAp0aGUgb2RkcyBvZiAkWSA9IDEkIGlzIGRlZmluZWQgYXMgJFxmcmFje1AoWSA9IDEpfXtQKFkgPSAwKX0gPSBcZnJhY3tQKFkgPSAxKX17MSAtIFAoWSA9IDEpfSQuCldlIGNhbiByZS1hcnJhbmdlIHRoZSBsb2dpc3RpYyBtb2RlbCBlcXVhdGlvbjoKCiQkClxiZWdpbnthbGlnbmVkfQpcbG4gXEJpZ2dbIFxmcmFje1AoWSA9IDEpfXsxIC0gUChZID0gMSl9IFxCaWdnXSAKJj0gXGxuIFxCaWdnWyBcZnJhY3tcZnJhY3sxfXsxICsgZV57LVhcYmV0YX19fXtcZnJhY3tlXnstWFxiZXRhfX17MSArIGVeey1YXGJldGF9fX0gXEJpZ2ddIFxcCiY9IFxsbigxICsgZV57LVhcYmV0YX0pIC0gXGxuIGVeey1YXGJldGF9KDEgKyBlXnstWFxiZXRhfSkgXFwKJj0gXGxuKDEgKyBlXnstWFxiZXRhfSkgLSBcbG4gZV57LVhcYmV0YX0gLSBcbG4oMSArIGVeey1YXGJldGF9KSBcXAomPSAtIFxsbiBlXnstWFxiZXRhfSBcXAomPSBYXGJldGEuClxlbmR7YWxpZ25lZH0KJCQKClRoYXQgaXMsCnRoZSBtb2RlbCB3ZWlnaHRzIGFyZSBsaW5lYXIgaW4gdGhlIGxvZy1vZGRzIG9mIG91ciB0YXJnZXQgb3V0Y29tZS4KCldoZW4gdGhlIHByb2JhYmlsaXR5IGlzIHRyYW5zZm9ybWVkIGludG8gb2RkcywKdGhlIHJhbmdlIGlzIHRyYW5zZm9ybWVkIGZyb20gJFswLDFdJCB0byAkWzAsXGluZnR5XSQuCgpgYGB7cHl0aG9uIGxvZ2l0X3Byb2Jfb2Rkc19wbG90fQojIFdlIHBsb3Qgb25seSB1cCB0byAuOTUgc2luY2UgdGhlIHZhbHVlIG9mIG9kZHMgd2lsbCBncm93IHVuYm91bmRlZGx5Lgpwcm9iID0gbnAubGluc3BhY2UoLjAwMSwgLjk1LCBudW09MTAwKQpvZGRzID0gcHJvYiAvICgxIC0gcHJvYikKbG9nX29kZHMgPSBucC5sb2cob2RkcykKCm9maWxlID0gInBsb3RzL3Byb2Jfb2Rkcy5odG1sIgpwID0gcGxvdF9vZmZsaW5lKAogIG9maWxlPW9maWxlLAogIGRhdGE9W2dvLlNjYXR0ZXIoeD1wcm9iLCB5PW9kZHMpXSwKICBsYXlvdXQ9Z28uTGF5b3V0KAogICAgdGl0bGU9IkV2ZW50IFByb2JhYmlsaXRpZXMgdG8gT2RkcyIsCiAgICB4YXhpcz1kaWN0KHRpdGxlPSJQcm9iYWJpbGl0eSIpLAogICAgeWF4aXM9ZGljdCh0aXRsZT0iT2RkcyIpKSkKYGBgCgpgYGB7ciwgZWNobz1GQUxTRX0KaHRtbHRvb2xzOjppbmNsdWRlSFRNTChweSRvZmlsZSkKYGBgCgpJZiB3ZSBmdXJ0aGVyIHRyYW5zZm9ybSBvZGRzIHRvIGxvZy1vZGRzLAp0aGUgcmFuZ2UgaXMgdHJhbnNmb3JtZWQgZnJvbSAkWzAsXGluZnR5XSQgdG8gJFstXGluZnR5LFxpbmZ0eV0kLgoKYGBge3B5dGhvbiBsb2dpdF9vZGRzX2xvZ29kZHNfcGxvdH0Kb2ZpbGUgPSAicGxvdHMvcHJvYl9vZGRzLmh0bWwiCnAgPSBwbG90X29mZmxpbmUoCiAgb2ZpbGU9b2ZpbGUsCiAgZGF0YT1bZ28uU2NhdHRlcih4PW9kZHMsIHk9bG9nX29kZHMpXSwKICBsYXlvdXQ9Z28uTGF5b3V0KAogICAgdGl0bGU9IkV2ZW50IE9kZHMgdG8gTG9nLU9kZHMiLAogICAgeGF4aXM9ZGljdCh0aXRsZT0iT2RkcyIpLAogICAgeWF4aXM9ZGljdCh0aXRsZT0iTG9nLU9kZHMiKSkpCmBgYAoKYGBge3IsIGVjaG89RkFMU0V9Cmh0bWx0b29sczo6aW5jbHVkZUhUTUwocHkkb2ZpbGUpCmBgYAoKUHV0IGl0IHRvZ2V0aGVyIGlzIHRoZSBlZmZlY3Qgb2YgdGhlIHNpZ21vaWQgZnVuY3Rpb246CgpgYGB7cHl0aG9uIGxvZ2l0X3NpZ21vaWRfcGxvdH0KIyBOb3RlIHRoYXQgaW5zdGVhZCBvZiBjb2RpbmcgcyA9IDEgLyAoMSArIG5wLmV4cCgtdCkpLAojIHdoaWNoIGlzIG51bWVyaWNhbGx5IHVuc3RhYmxlLAojIHdlIHNob3VsZCB1c2UgYSBtYXRoIHRyaWNrIHRvIG1ha2UgaXQgc3RhYmxlLgpkZWYgc2lnbW9pZCh0KToKICAiIiJOdW1lcmljYWxseSBzdGFibGUgc2lnbW9pZC4iIiIKICByZXR1cm4gbnAuZXhwKC1ucC5sb2dhZGRleHAoMCwgLXQpKQoKdCA9IG5wLmxpbnNwYWNlKC0xMCwgMTAsIG51bT0xMDApCm9maWxlID0gInBsb3RzL3NpZ21vaWQuaHRtbCIKcCA9IHBsb3Rfb2ZmbGluZSgKICBvZmlsZT1vZmlsZSwKICBkYXRhPVtnby5TY2F0dGVyKHg9dCwgeT1zaWdtb2lkKHQpKV0sCiAgbGF5b3V0PWdvLkxheW91dCgKICAgIHRpdGxlPSJBIFNpZ21vaWQgRnVuY3Rpb24iLAogICAgeGF4aXM9ZGljdCh0aXRsZT0iUmF3IFZhbHVlIiksCiAgICB5YXhpcz1kaWN0KHRpdGxlPSJQcm9iYWJpbGl0eSIpKSkKYGBgCgpgYGB7ciwgZWNobz1GQUxTRX0KaHRtbHRvb2xzOjppbmNsdWRlSFRNTChweSRvZmlsZSkKYGBgCgojIyMgQ3Jvc3MgRW50cm9weQoKSG93IGRvIHdlIHNvbHZlIGZvciB0aGUgbW9kZWwgd2VpZ2h0cyAkXGJldGEkIGluIGVxdWF0aW9uICRcZXFyZWZ7ZXE6bG9naXR9JD8KSW4gdGhlIGxpbmVhciByZWdyZXNzaW9uIG1vZGVsIHdlIHNvbHZlIGZvciB0aGUgd2VpZ2h0cyBieSBtaW5pbWl6aW5nIHRoZSBtZWFuIHNxdWFyZWQgZXJyb3IuCkluIGxvZ2lzdGljIHJlZ3Jlc3Npb24gbW9kZWwgd2UgbmVlZCB0byBkZWZpbmUgbWVhc3VyZW1lbnQgZm9yIG1vZGVsaW5nIGVycm9yIGFzIHdlbGwuCgpQdXQgaXQgZGlmZmVyZW50bHksCndlJ2QgbGlrZSB0byBjYWxjdWxhdGUgdGhlIGRpc3RhbmNlIGJldHdlZW4gb3VyIHByZWRpY3RlZCBwcm9iYWJpbGl0eSBhbmQgdGhlIHJlYWwgZXZlbnQgbGFiZWwgZGlzdHJpYnV0aW9uIChjYWxsZWQgdGhlICplbXBpcmljYWwgZGlzdHJpYnV0aW9uKikuCkluIGluZm9ybWF0aW9uIHRoZW9yeSB0aGUgY3Jvc3MgZW50cm9weSBpcyB1c2VkIHRvIG1lYXN1cmUgdGhlIGRpc3RhbmNlIGJldHdlZW4gdHdvIHByb2JhYmlsaXR5IGRpc3RyaWJ1dGlvbi4KClRoZSBbZW50cm9weV0oaHR0cHM6Ly9lbi53aWtpcGVkaWEub3JnL3dpa2kvRW50cm9weV8oaW5mb3JtYXRpb25fdGhlb3J5KSkgb2YgYSBkaXNjcmV0ZSBwcm9iYWJpbGl0eSBkaXN0cmlidXRpb24gaXMgZGVmaW5lZCBhczoKCiQkCkgocCkgPSAtIFxzdW1faSBwX2kgXGxvZ18ycF9pLAokJAoKd2hlcmUgJHBfaSQgaXMgdGhlIHByb2JhYmlsaXR5IGZvciBldmVudCAkaSQuCkl0IG1lYXN1cmVzIHRoZSB1bmNlcnRhaW50eSBvZiBhIHN0b2NoYXN0aWMgZXZlbnQuCgpUYWtlIGEgY29pbiBmbGlwIGV2ZW50IGFzIGV4YW1wbGUuCldlIHBsb3QgdGhlIGVudHJvcHkgdmFsdWUgYXQgZGlmZmVyZW50IHZhbHVlIG9mIGNvaW4gYmlhcyAodGhlIHByb2JhYmlsaXR5IG9mIGhhdmluZyBhIGhlYWQgaW5zdGVhZCBvZiBhIHRhaWwuKQoKYGBge3B5dGhvbiBsb2dpdF9jb2luX2ZsaXBfZW50cm9weV9wbG90fQpkZWYgZW50cm9weV9iaW5hcnkocCk6CiAgcmV0dXJuIC1wKm5wLmxvZzIocCkgLSAoMSAtIHApKm5wLmxvZzIoMSAtIHApCiAgCnByb2IgPSBucC5saW5zcGFjZSguMDEsIC45OSwgbnVtPTEwMCkKCm9maWxlID0gInBsb3RzL2VudHJvcHkuaHRtbCIKcCA9IHBsb3Rfb2ZmbGluZSgKICBvZmlsZT1vZmlsZSwKICBkYXRhPVtnby5TY2F0dGVyKHg9cHJvYiwgeT1lbnRyb3B5X2JpbmFyeShwcm9iKSldLAogIGxheW91dD1nby5MYXlvdXQoCiAgICB0aXRsZT0iRW50cm9weSBvZiBhIEJpbmFyeSBFdmVudCAoQ29pbiBGbGlwKSIsCiAgICB4YXhpcz1kaWN0KHRpdGxlPSJQcm9iYWJpbGl0eSBvZiBhIEhlYWQiKSwKICAgIHlheGlzPWRpY3QodGl0bGU9IkVudHJvcHkiKSkpCmBgYAoKYGBge3IsIGVjaG89RkFMU0V9Cmh0bWx0b29sczo6aW5jbHVkZUhUTUwocHkkb2ZpbGUpCmBgYAoKSXQgaXMgb2J2aW91cyB0aGF0IHRoZSBlbnRyb3B5IG9mIHRoaXMgZXZlbnQgaXMgbWF4aW1pemVkIHdoZW4gdGhlIHByb2JhYmlsaXR5IG9mIGZsaXBwaW5nIGEgaGVhZCBpcyBleGFjdGx5IDAuNS4KQXQgdGhpcyBsZXZlbCB0aGUgZXZlbnQgaGFzIGEgaGlnaGVzdCBsZXZlbCBvZiB1bmNlcnRhaW50eSBpbiBhIHNlbnNlIHRoYXQgaXQgaXMgdGhlIG1vc3QgZGlmZmljdWx0IGNhc2UgdG8gcHJlZGljdCB0aGUgb3V0Y29tZSBvZiBhIGZsaXAuCgpOb3cgbW92ZSBvbiB0byBjcm9zcyBlbnRyb3B5LgpDcm9zcyBlbnRyb3B5IGJldHdlZW4gdHdvIGRpc2NyZXRlIHByb2JhYmlsaXR5IGRpc3RyaWJ1dGlvbiAkcCQgYW5kICRxJCBvdmVyIHRoZSBzYW1lIHN1cHBvcnQgaXMgZGVmaW5lZCBhczoKCiQkCkgocCwgcSkgPSAtIFxzdW1faSBwX2kgXGxvZ18ycV9pLgokJAoKRm9yIG91ciBsb2dpc3RpYyByZWdyZXNzaW9uIG1vZGVsLApkaXN0cmlidXRpb24gJHAkIGlzIHRoZSBlbXBpcmljYWwgZGlzdHJpYnV0aW9uIChsYWJlbCBkaXN0cmlidXRpb24pIGFuZCBkaXN0cmlidXRpb24gJHEkIGlzIG91ciBtb2RlbCBwcmVkaWN0ZWQgZGlzdHJpYnV0aW9uLgpEZW5vdGUgJHFfaSA9IFAoeV9pID0gMSkkIGZvciB0aGUgcHJlZGljdGlvbiBvZiAkaSQtdGggZXhhbXBsZS4KVGhlIGNyb3NzLWVudHJvcHktbG9zcyBvZiBvdXIgbW9kZWwgaGVuY2UgY2FuIGJlIHdyaXR0ZW4gYXM6CgokJApcbWJveHtDcm9zcy1FbnRyb3B5IExvc3N9ID0gLSBcZnJhY3sxfXtOfVxzdW1faV5OIFxiaWdnWyB5X2lcbG9nXzJxX2kgKyAoMSAtIHlfaSlcbG9nXzIoMSAtIHFfaSlcYmlnZ10sCiQkCgp3aGVyZSAkeV9pIFxpbiBcezAsMVx9JCBpcyB0aGUgJGkkLXRoIGJpbmFyeSB0cmFpbmluZyBsYWJlbCBhbmQgJFAoeV9pID0gMSkkIHRoZSBtb2RlbCBwcmVkaWN0aW9uIGZvciB0aGUgJGkkLXRoIGV4YW1wbGUgb3V0IG9mICROJCB0b3RhbCB0cmFpbmluZyBleGFtcGxlcy4KVGhpcyBpcyB0aGUgbWVhbiB2YWx1ZSBvZiBjcm9zcyBlbnRyb3B5IGZvciBlYWNoIHRyYWluaW5nIGV4YW1wbGUuCgpTaW5jZSAkcV9pID0gUCh5X2kgPSAxKSQgaXMgZXhwcmVzc2VkIGJ5IG91ciBtb2RlbCBlcXVhdGlvbiAkXGVxcmVme2VxOmxvZ2l0fSQsCm5vdyB3ZSBjYW4gYXBwbHkgZ3JhZGllbnQgZGVzY2VudCB0byB0aGUgbG9zcyBmdW5jdGlvbiB0byBmaW5kIG91dCB0aGUgb3B0aW11bSBtb2RlbCB3ZWlnaHRzIHRoYXQgbWluaW1pemUgdGhlIGNyb3NzLWVudHJvcHkgbG9zcy4KCiMjIyBNYXhpbXVtIExpa2VsaWhvb2QgRXN0aW1hdG9yCgpCZWZvcmUgd2UgaW1wbGVtZW50IG91ciBvcHRpbWl6ZXIgZm9yIGEgbG9naXN0aWMgcmVncmVzc2lvbiBtb2RlbCwKd2UgZGVtb25zdHJhdGUgdGhhdCBtaW5pbWl6aW5nIGNyb3NzIGVudHJvcHkgaXMgaW5kZWVkIGVxdWl2YWxlbnQgdG8gbWF4aW1pemluZyBkYXRhIGxpa2VsaWhvb2QuCgpUaGUgZGF0YSBsaWtlbGlob29kIGlzIGp1c3QgdGhlIHByb2R1Y3Qgb2YgYWxsIHByZWRpY3RlZCBwcm9iYWJpbGl0aWVzIGZvciBpbmRpdmlkdWFsIGV4YW1wbGUsCnByb3ZpZGVkIHRoYXQgdGhleSBhcmUgaW5kZXBlbmRlbnQuCgokJApcbWJveHtsaWtlbGlob29kfSA9IFxwcm9kX2leTiBxX2lee3lfaX0oMSAtIHFfaSleezEgLSB5X2l9LgokJAoKVGhlIG1heGltdW0gbGlrZWxpaG9vZCBlc3RpbWF0b3Igd2lsbCB0cnkgdG8gbWF4aW1pemUgdGhlIGxvZyBvZiB0aGUgbGlrZWxpaG9vZCwKd2hpY2ggaXM6CgokJApcYmVnaW57YWxpZ25lZH0KXG1ib3h7bG9nLWxpa30gCiY9IFxsb2dfMiBccHJvZF9pXk4gcV9pXnt5X2l9KDEgLSBxX2kpXnsxIC0geV9pfSBcXAomPSBcc3VtX2leTiBcbG9nXzIgcV9pXnt5X2l9KDEgLSBxX2kpXnsxIC0geV9pfSBcXAomPSBcc3VtX2leTiBcYmlnZ1sgeV9pXGxvZ18yIHFfaSArICgxIC0geV9pKVxsb2dfMigxIC0gcV9pKSBcYmlnZ10uClxlbmR7YWxpZ25lZH0KJCQKCkJ5IHRha2luZyB0aGUgYXZlcmFnZSBhcyB3ZWxsLAp0aGUgbmVnYXRpdmUgbG9nLWxpa2VsaWhvb2QgaXMgZXhhY3RseSB0aGUgY3Jvc3MgZW50cm9weS4KCiMjIyBHcmFkaWVudCBEZXNjZW50IHdpdGggTG9nIExvc3MKCk5vdyBsZXQncyBhbHNvIGltcGxlbWVudCBhIGJhdGNoIGdyYWRpZW50IGRlc2NlbnQgb3B0aW1pemVyIGZvciBhIGxvZ2lzdGljIHJlZ3Jlc3Npb24gbW9kZWwuCldlIHdpbGwgdXNlIHRoZSBzYW1lIHRveSBleGFtcGxlIGFuZCBjcmVhdGUgYWRkaXRpb25hbCByYW5kb20gYmluYXJ5IGxhYmVscyBmb3IgdGhpcyBleGVyY2lzZS4KCmBgYHtweXRob24gbG9naXRfZmFrZV9kYXRhfQp5MiA9IG5wLmFycmF5KFtucC5yYW5kb20uYmlub21pYWwoMSwgdikgZm9yIHYgaW4gc2lnbW9pZChYLmRvdChiZXRhKSldKQpgYGAKClRoZSBncmFkaWVudCBmdW5jdGlvbiBtdXN0IGJlIGRlcml2ZWQgd2l0aCByZXNwZWN0IHRvIG1vZGVsIHdlaWdodHMuClRvIHNpbXBsaWZ5IHRoZSBtYXRoIHdlIHJlcGxhY2UgbG9nIG9mIGJhc2UgMiB3aXRoIG5hdHVyYWwgbG9nICh3aXRoIG5vIGltcGFjdCBvbiB0aGUgb3B0aW1pemF0aW9uKSwKYW5kIHdlIHRha2UgYWR2YW50YWdlIG9mIHRoZSBmYWN0IHRoYXQgdGhlIGRlcml2YXRpdmUgb2YgdGhlIHNpZ21vaWQgZnVuY3Rpb24gaXM6XltIZXJlIHdlIHVzZSB0aGUgY29tbW9uIGRlcml2YXRpdmVzOiAkXGZyYWN7ZGYoeClebn17ZHh9ID0gbmYoeClee24tMX1mJyh4KSQgYW5kICRcZnJhY3tkZV57Zih4KX19e2R4fSA9IGYnKHgpZV57Zih4KX0uJF0KCiQkClxiZWdpbnthbGlnbmVkfQpcZnJhY3tkcyh0KX17ZHR9CiY9IFxmcmFje2RcZnJhY3sxfXsxICsgZV57LXR9fX17ZHR9IFxcCiY9IC0oMSArIGVeey10fSleey0yfSBcY2RvdCAoLSBlXnstdH0pIFxcCiY9IFxmcmFje2Veey10fX17KDEgKyBlXnstdH0pXjJ9IFxcCiY9IFxmcmFjezF9ezEgKyBlXnstdH19IFxjZG90IFxmcmFje2Veey10fX17MSArIGVeey10fX0gXFwKJj0gcyh0KSBcY2RvdCBbMSAtIHModCldLgpcZW5ke2FsaWduZWR9CiQkCgpUaGUgZ3JhZGllbnQgaW4gb3VyIHVuaXZhcmlhdGUgbW9kZWwgdy5yLnQuIHRoZSBiaWFzIHRlcm0gd2lsbCBiZTpeW0hlcmUgd2UgdXNlIHRoZSBjb21tb24gZGVyaXZhdGl2ZSAkXGZyYWN7ZFxsbiBmKHgpfXtkeH0gPSBcZnJhY3tmJyh4KX17Zih4KX0kIGFuZCB0aGUgW2NoYWluIHJ1bGVdKGh0dHBzOi8vZW4ud2lraXBlZGlhLm9yZy93aWtpL0NoYWluX3J1bGUpIHRvIGhhbmRsZSB0aGUgdGVybSAkXGZyYWN7XHBhcnRpYWxcbG4gcV9pfXtccGFydGlhbFxiZXRhXzB9JCB3aGVyZSAkcV9pJCBpcyB0aGUgc2lnbW9pZCBjb21wdXRlZCBmb3IgdGhlICRpJC10aCBleGFtcGxlLl0KCiQkClxiZWdpbnthbGlnbmVkfQpcZnJhY3tccGFydGlhbFxtYm94e0xvZ0xvc3N9fXtccGFydGlhbFxiZXRhXzB9IAomPSAtIFxmcmFjezF9e059XHN1bV9pIFxiaWdnWyB5X2lcZnJhY3tccGFydGlhbFxsbiBxX2l9e1xwYXJ0aWFsXGJldGFfMH0gKyAKICAoMSAtIHlfaSlcZnJhY3tccGFydGlhbFxsbigxIC0gcV9pKX17XHBhcnRpYWxcYmV0YV8wfVxiaWdnXSBcXAomPSAtIFxmcmFjezF9e059XHN1bV9pIFxiaWdnWyB5X2lcZnJhY3sxfXtxX2l9XGZyYWN7XHBhcnRpYWwgcV9pfXtccGFydGlhbFxiZXRhXzB9ICsgCiAgKDEgLSB5X2kpXGZyYWN7MX17MSAtIHFfaX1cZnJhY3tccGFydGlhbCgxIC0gcV9pKX17XHBhcnRpYWxcYmV0YV8wfVxiaWdnXSBcXAomPSAtIFxmcmFjezF9e059XHN1bV9pIFxiaWdnWyB5X2lcZnJhY3sxfXtxX2l9XGZyYWN7XHBhcnRpYWwgKFxiZXRhXzAgKyBcYmV0YV8xeF9pKX17XHBhcnRpYWxcYmV0YV8wfVxmcmFje1xwYXJ0aWFsIHFfaSh0KX17XHBhcnRpYWwgdH0gLSAKICAoMSAtIHlfaSlcZnJhY3sxfXsxIC0gcV9pfVxmcmFje1xwYXJ0aWFsIChcYmV0YV8wICsgXGJldGFfMXhfaSl9e1xwYXJ0aWFsXGJldGFfMH1cZnJhY3tccGFydGlhbCBxX2kodCl9e1xwYXJ0aWFsIHR9XGJpZ2ddIFxcCiY9IC0gXGZyYWN7MX17Tn1cc3VtX2kgXGJpZ2dbIHlfaVxmcmFjezF9e3FfaX1xX2koMSAtIHFfaSkgLSAKICAoMSAtIHlfaSlcZnJhY3sxfXsxIC0gcV9pfXFfaSgxIC0gcV9pKVxiaWdnXSBcXAomPSAtIFxmcmFjezF9e059XHN1bV9pIFxiaWdnWyB5X2koMSAtIHFfaSkgLSAoMSAtIHlfaSlxX2kgXGJpZ2ddIFxcCiY9IC0gXGZyYWN7MX17Tn1cc3VtX2kgKHlfaSAtIHFfaSkuClxlbmR7YWxpZ25lZH0KJCQKClNpbWlsYXJ5IGZvciB0aGUgd2VpZ2h0OgoKJCQKXGZyYWN7XHBhcnRpYWxcbWJveHtMb2dMb3NzfX17XHBhcnRpYWxcYmV0YV8xfQo9IC0gXGZyYWN7MX17Tn1cc3VtX2kgKHlfaSAtIHFfaSl4X2kuCiQkCgpOb3cgdGhlIFB5dGhvbiBjb2RlIGZvciBiYXRjaCBncmFkaWVudCBkZXNjZW50IHdpdGggbG9nLWxvc3M6CgpgYGB7cHl0aG9uIGxvZ2l0X2dkfQpkZWYgbG9nbG9zcyhYLCB5LCBiKToKICBsb2dsb3NzX3BvcyA9IHkgKiBucC5sb2coc2lnbW9pZChYLmRvdChiKSkpCiAgbG9nbG9zc19uZWcgPSAoMSAtIHkpICogbnAubG9nKDEgLSBzaWdtb2lkKFguZG90KGIpKSkKICByZXR1cm4gLSAobG9nbG9zc19wb3MgKyBsb2dsb3NzX25lZykubWVhbigpCgpkZWYgbG9naXRfZ3JhZF9mdW5jKFgsIHksIGIpOgogIHJldHVybiAtICh5IC0gc2lnbW9pZChYLmRvdChiKSkpLmRvdChYKSAvIFguc2hhcGVbMF0KCmRlZiBjcm9zc19lbnRyb3B5X2dkX29wdGltaXplKFgsIHksIGxyPS4wMSwgbl9zdGVwPTEwMCwgYmF0Y2hfc2l6ZT02NCk6CiAgYiA9IG5wLnJhbmRvbS5ub3JtYWwoc2l6ZT1YLnNoYXBlWzFdKQogIGwgPSBbbG9nbG9zcyhYLCB5LCBiKV0KICBmb3Igc3RlcCBpbiByYW5nZShuX3N0ZXApOgogICAgc2lkID0gbnAucmFuZG9tLnJhbmRpbnQoWC5zaGFwZVswXSwgc2l6ZT1iYXRjaF9zaXplKQogICAgWGIgPSBYW3NpZCw6XQogICAgeWIgPSB5W3NpZF0KICAgIGIgLT0gbHIqbG9naXRfZ3JhZF9mdW5jKFhiLCB5YiwgYikKICAgIGwuYXBwZW5kKGxvZ2xvc3MoWGIsIHliLCBiKSkKICByZXR1cm4gYiwgbAoKbG9nX2JldGEsIGxvZ19sb3NzID0gY3Jvc3NfZW50cm9weV9nZF9vcHRpbWl6ZShYLCB5MiwgbHI9LjAxLCBuX3N0ZXA9MzAwMCkKcHJpbnQobG9nX2JldGEpCmBgYAoKYGBge3B5dGhvbiBsb2dpdF9sb3NzX3Bsb3R9Cm9maWxlID0gInBsb3RzL3RveV9sb2dfbG9zcy5odG1sIgpwZGF0YSA9IFtnby5TY2F0dGVyKHg9bnAuYXJhbmdlKGxlbihsb2dfbG9zcykpLCB5PWxvZ19sb3NzKV0KcCA9IHBsb3Rfb2ZmbGluZSgKICBvZmlsZT1vZmlsZSwKICBkYXRhPXBkYXRhLAogIGxheW91dD1nby5MYXlvdXQoCiAgICB0aXRsZT0iVHJhY2Ugb2YgVHJhaW5pbmcgTG9nLUxvc3MiLAogICAgeGF4aXM9ZGljdCh0aXRsZT0iU3RlcCIpLAogICAgeWF4aXM9ZGljdCh0aXRsZT0iTG9zcyIpKSkKYGBgCgpgYGB7ciwgZWNobz1GQUxTRX0KaHRtbHRvb2xzOjppbmNsdWRlSFRNTChweSRvZmlsZSkKYGBgCgpDb21wYXJpbmcgdG8gbGluZWFyIHJlZ3Jlc3Npb24sCmEgbG9naXN0aWMgcmVncmVzc2lvbiBtb2RlbCBpcyBoYXJkZXIgdG8gY29udmVyZ2UuClNpbmNlIG91ciBuYWl2ZSBpbXBsZW1lbnRhdGlvbiBkb2VzIG5vdCBkbyBjb252ZXJnZW5jZSBkaWFnbm9zdGljcywKbGV0J3MgdXNlIFIncyBidWlsdC1pbiBgZ2xtYCBmdW5jdGlvbiB3aGljaCB1c2UgTmV3dG9uJ3MgbWV0aG9kIChhIDJuZC1vcmRlciBvcHRpbWl6ZXIgdXRpbGl6aW5nIG5vdCBvbmx5IDFzdC1vcmRlciBidXQgYWxzbyAybmQtb3JkZXIgZGVyaXZhdGl2ZXMpIHRvIGNoZWNrIHRoZSBlc3RpbWF0aW9uIHJlc3VsdCBvZiBvdXIgdG95IGV4YW1wbGU6CgpgYGB7ciBsb2dpdF9jaGVja19zb2x1dGlvbn0KIyBUaGlzIGlzIFIgY29kZS4KY29lZihnbG0oeSB+IHgsIGRhdGE9ZGF0YS5mcmFtZSh5PXB5JHkyLCB4PXB5JFhbLDJdKSwgZmFtaWx5PWJpbm9taWFsKSkKYGBgCgpOb3cgaW5jcmVhc2UgYm90aCB0aGUgbGVhcm5pbmcgcmF0ZSBhbmQgdHJhaW5pbmcgc3RlcCBvZiBvdXIgbmFpdmUgZ3JhZGllbnQgZGVzY2VudCBvcHRpbWl6ZXI6CgpgYGB7cHl0aG9ufQpwcmludChjcm9zc19lbnRyb3B5X2dkX29wdGltaXplKFgsIHkyLCBscj0uNSwgbl9zdGVwPTUwMDApWzBdKQpgYGAKClNlZW1zIGJldHRlci4KCk9yIHdlIGNhbiB1c2UgdGhlIFB5dGhvbiBwYWNrYWdlIGBzdGF0c21vZGVsc2AgKHdoaWNoIGFsc28gdXNlcyBhIDJuZC1vcmRlciBvcHRpbWl6ZXIgYnkgZGVmYXVsdCkgdG8gY2hlY2sgb3VyIHJlc3VsdDogCgpgYGB7cHl0aG9ufQppbXBvcnQgc3RhdHNtb2RlbHMuYXBpIGFzIHNtCnNtLkxvZ2l0KHkyLCBYKS5maXQoKS5zdW1tYXJ5KCkKYGBgCgpPciB3ZSBjYW4gdXNlIHRoZSBwb3B1bGFyIG1hY2hpbmUgbGVhcm5pbmcgbGlicmFyeSBgc2tsZWFybmAgdG8gZG8gdGhlIHNhbWUgY2hlY2s6CgpgYGB7cHl0aG9ufQpmcm9tIHNrbGVhcm4ubGluZWFyX21vZGVsIGltcG9ydCBMb2dpc3RpY1JlZ3Jlc3Npb24KIyBXZSBuZWVkIHRvIHNldCBDIHRvIGFuIGFyYml0cmFyaWx5IGxhcmdlIG51bWJlciB0byBzdXBwcmVzcyByZWd1bGFyaXphdGlvbgojIHNpbmNlIG91ciBuYWl2ZSBhcHByb2FjaCBkb2Vzbid0IGltcGxlbWVudCBhbnkgcmVndWxhcml6YXRpb24uCkxvZ2lzdGljUmVncmVzc2lvbihDPTFlMTYsIGZpdF9pbnRlcmNlcHQ9RmFsc2UpLmZpdChYLCB5MikuY29lZl8KYGBgCgojIEF1dG9tYXRpYyBEaWZmZXJlbnRpYXRpb24KCkluIHRoZSBwcmV2aW91cyBzZWN0aW9uIHdlIGltcGxlbWVudCBhIHNpbXBsZSBncmFkaWVudCBkZXNjZW50IG9wdGltaXplciBieSBtYW51YWxseSBkZXJpdmUgdGhlIGZ1bmN0aW9uYWwgZm9ybSBvZiBncmFkaWVudCBvbiBvdXIgb3duLgpUaGlzIGNvdWxkIGJlIHRyb3VibGVzb21lIGlmIG91ciBtb2RlbCBiZWNvbWVzIG1vcmUgYW5kIG1vcmUgY29tcGxpY2F0ZWQsCmFzIGluIHRoZSBjYXNlIG9mIGEgZGVlcCBuZXVyYWwgbmV0LgoKQXV0b21hdGNpIGRpZmZlcmVudGlhdGlvbiBpcyBhIHByb2dyYW1taW5nIHRlY2huaXF1ZSB0byBjYWxjdWxhdGUgdGhlIGdyYWRpZW50IG9mIGFueSBnaXZlbiBmdW5jdGlvbi4KT25lIG9mIHRoZSBtb3N0IHBvcHVsYXIgbGlicmFyeSBmb3IgdGhpcyBwdXJwb3NlIGlzIFtUZW5zb3JGbG93XShodHRwczovL2dpdGh1Yi5jb20vdGVuc29yZmxvdy90ZW5zb3JmbG93KS4KCkxldCdzIHVzZSBgdGVuc29yZmxvd2AgdG8gaW1wbGVtZW50IG91ciBzaW1wbGUgZ3JhZGllbnQgZGVzY2VudCBvcHRpbWl6ZXIgYWdhaW4uCkJ1dCB0aGlzIHRpbWUgd2Ugd2lsbCBOT1QgZXhwbGljaXRseSBkZXJpdmUgdGhlIGdyYWRpZW50IGZ1bmN0aW9uLgpJbnN0ZWFkLAp3ZSB3aWxsIG9ubHkgc3BlY2lmeSB0aGUgdGFyZ2V0IGZ1bmN0aW9uIHdoaWNoIGlzIGp1c3QgdGhlIGxvc3MgZnVuY3Rpb24gb2Ygb3VyIG1vZGVsLgoKYGBge3B5dGhvbiB0Zl9hZH0KaW1wb3J0IHRlbnNvcmZsb3cgYXMgdGYKdGYuZW5hYmxlX2VhZ2VyX2V4ZWN1dGlvbigpCgojIFVzZSB0ZW5zb3IgdG8gcmVwcmVzZW50IG91ciBkYXRhLgojIE5vdGUgdGhhdCB3ZSBuZWVkIHRvIGJlIHZlcnkgc3BlY2lmaWMgYWJvdXQgZHR5cGUvc2hhcGUgb2Ygb3VyIHRlbnNvcnMuClhfdGYgPSB0Zi5jb252ZXJ0X3RvX3RlbnNvcihYLCBkdHlwZT10Zi5mbG9hdDMyKQpiZXRhX3RmID0gdGYucmVzaGFwZSh0Zi5jb252ZXJ0X3RvX3RlbnNvcihiZXRhLCBkdHlwZT10Zi5mbG9hdDMyKSwgKDIsMSkpCmVfdGYgPSB0Zi5yZXNoYXBlKHRmLmNvbnZlcnRfdG9fdGVuc29yKGUsIGR0eXBlPXRmLmZsb2F0MzIpLCAoTiwgMSkpCnlfdGYgPSB0Zi5tYXRtdWwoWF90ZiwgYmV0YV90ZikgKyBlX3RmCnkyX3RmID0gdGYucmVzaGFwZSh0Zi5jb252ZXJ0X3RvX3RlbnNvcih5MiwgZHR5cGU9dGYuZmxvYXQzMiksIChOLCAxKSkKCmRlZiBsb3NzX21zZV90ZihYLCB5LCBiZXRhKToKICB5X2hhdCA9IHRmLm1hdG11bChYLCBiZXRhKQogIHJldHVybiB0Zi5yZWR1Y2VfbWVhbihpbnB1dF90ZW5zb3IgPSAoeV9oYXQgLSB5KSoqMikKCmRlZiBsb2dsb3NzX3RmX2JhZChYLCB5LCBiZXRhKToKICAjIFRoaXMgY2FuIHN1ZmZlciBmcm9tIG51bWVyaWNhbCBzdGFiaWxpdHkgaXNzdWUuCiAgbG9nbG9zc19wb3MgPSB5ICogdGYubG9nKHRmLnNpZ21vaWQodGYubWF0bXVsKFgsIGJldGEpKSkKICBsb2dsb3NzX25lZyA9ICgxIC0geSkgKiB0Zi5sb2coMSAtIHRmLnNpZ21vaWQodGYubWF0bXVsKFgsIGJldGEpKSkKICByZXR1cm4gLSB0Zi5yZWR1Y2VfbWVhbihsb2dsb3NzX3BvcyArIGxvZ2xvc3NfbmVnKQoKZGVmIGxvZ2xvc3NfdGYoWCwgeSwgYmV0YSk6CiAgIyB0Zi5zaWdtb2lkIGlzIG5vdCBudW1lcmljYWxseSBzdGFibGUuCiAgIyBCdXQgdGhlcmUgaXMgYSBjb252ZW5pZW50IGZ1bmN0aW9uIHRvIGRvIHRoZSBjcm9zcyBlbnRyb3B5IGNhbGN1bGF0aW9uIHN0YWJseS4KICBzID0gdGYubm4uc2lnbW9pZF9jcm9zc19lbnRyb3B5X3dpdGhfbG9naXRzKGxhYmVscz15LCBsb2dpdHM9dGYubWF0bXVsKFgsIGJldGEpKQogIHJldHVybiB0Zi5yZWR1Y2VfbWVhbihzKQoKZGVmIGdkX29wdGltaXplX3RmKFgsIHksIGxvc3NfZnVuYywgbHI9LjAxLCBuX3N0ZXA9MTAwKToKICBncmFkX2Z1bmNfdGYgPSB0Zi5jb250cmliLmVhZ2VyLmdyYWRpZW50c19mdW5jdGlvbihsb3NzX2Z1bmMsIHBhcmFtcz1bMl0pCiAgYmV0YSA9IHRmLnJhbmRvbV9ub3JtYWwoKDIsIDEpKQogIGZvciBzdGVwIGluIHJhbmdlKG5fc3RlcCk6CiAgICBncmFkID0gZ3JhZF9mdW5jX3RmKFgsIHksIGJldGEpWzBdCiAgICBiZXRhIC09IGxyICogZ3JhZAogIHJldHVybiBiZXRhLm51bXB5KCkKCiMgRm9yIHRoZSBNU0UgbG9zcyBwcm9ibGVtLgpwcmludChnZF9vcHRpbWl6ZV90ZihYX3RmLCB5X3RmLCBsb3NzX2Z1bmM9bG9zc19tc2VfdGYsIG5fc3RlcD0zMDAwKSkKCiMgRm9yIHRoZSBjcm9zcyBlbnRyb3B5IGxvc3MgcHJvYmxlbS4KcHJpbnQoZ2Rfb3B0aW1pemVfdGYoWF90ZiwgeTJfdGYsIGxvc3NfZnVuYz1sb2dsb3NzX3RmLCBscj0uNSwgbl9zdGVwPTUwMDApKQpgYGAKCkluIHRoZSBhYm92ZSBjb2RpbmcgZXhhbXBsZSBvbmUgc2hvdWxkIHJlYWxpemUgdGhhdCB3ZSBubyBsb25nZXIgbmVlZCB0byBoYXJkY29kZSB0aGUgZnVuY3Rpb25hbCBmb3JtIG9mIHRoZSBncmFkaWVudHMuCkluc3RlYWQgd2UganVzdCBwbHVnLWluIHRoZSBsb3NzIGZ1bmN0aW9uIGFuZCBsZXQgYHRlbnNvcmZsb3dgIHRvIGRvIHRoZSBncmFkaWVudCBjYWxjdWxhdGlvbiBmb3IgdXMuCgpPZiBjb3Vyc2UgaW4gYWN0dWFsIGRldmVsb3BtZW50IHdlIHdpbGwgdXNlIGhpZ2hlci1sZXZlbCBBUElzIHRvIGltcGxlbWVudCBvdXIgbW9kZWwsCndoZXJlIHRoZSBlbnRpcmUgb3B0aW1pemF0aW9uIHByb2Nlc3MgaXMgYWJzdHJhY3RlZCBhd2F5IGZyb20gdGhlIGFwcGxpY2F0aW9uIGNvZGUuCgojIE5ldXJhbCBOZXR3b3JrcwoKQm90aCBsaW5lYXIgcmVncmVzc2lvbiBhbmQgbG9naXN0aWMgcmVncmVzc2lvbiBjYW4gYmUgY29uc2lkZXJlZCBhcyBzaW1wbGUgYWRkaXRpdmUgbW9kZWwgb2YgdGhlIGZvcm06CgokJApcaGF0e3l9ID0gXFBoaVxiaWdnKFxzdW1fe2k9MX1eUHdfaXhfaVxiaWdnKSwKJCQKCndoZXJlICRQJCBpcyB0aGUgbnVtYmVyIG9mIGZlYXR1cmVzIHVzZWQsCiR4X2kkIGlzIHRoZSAkaSQtdGggZmVhdHVyZSwKYW5kICRcUGhpKFxjZG90KSQgaXMgYSBmdW5jdGlvbiBhcHBsaWVkIHRvIHRoZSBvdXRwdXQuCkluIGxpbmVhciByZWdyZXNzaW9uICRcUGhpKFxjZG90KSQgaXMgc2ltcGx5IGFuIGlkZW50aXR5IGZ1bmN0aW9uLgpJbiBsb2dpc3RpYyByZWdyZXNzaW9uICRcUGhpKFxjZG90KSQgaXMgdGhlIHN0YW5kYXJkIHNpZ21vaWQgZnVuY3Rpb24uCgpOb3cgY29uc2lkZXIgdGhlcmUgaXMgYSB3YXkgdG8gZW5zZW1ibGUgbXVsdGlwbGUgc3VjaCBhZGRpdGl2ZSBtb2RlbHMgdG9nZXRoZXIgdG8gZ2VuZXJhdGUgYSBwb3RlbnRpYWxseSBiZXR0ZXIgYW5kIG1vcmUgc29waGlzdGljYXRlZCBtb2RlbC4KV2UgdXNlIHRoZSBmb2xsb3dpbmcgZGlhZ3JhbSBmb3IgaWxsdXN0cmF0aW9uLgoKYGBge3Igbm5fZGlhZ3JhbSwgZWNobz1GQUxTRX0KIyBEcmF3IGEgc2ltcGxlIG5ldXJhbCBuZXRzLgpEaWFncmFtbWVSOjpnclZpeigiCmRpZ3JhcGggc3Vic2NyaXB0IHsKCiAgZ3JhcGggW2xheW91dCA9IGRvdCByYW5rZGlyID0gTFIgb3JkZXJpbmcgPSBpbiByYW5rc2VwPTIgc3BsaW5lcz10cnVlXQoKICBub2RlIFtzaGFwZSA9IGNpcmNsZV0KCiAgc3ViZ3JhcGggY2x1c3Rlcl9pbnB1dF9sYXllciB7CiAgICBsYWJlbCA9ICdJbnB1dCBMYXllcicKICAgIHgxIFtsYWJlbCA9ICd4QF97MX0nXQogICAgeDIgW2xhYmVsID0gJ3hAX3syfSddCiAgICB4MyBbbGFiZWwgPSAneEBfezN9J10KICB9CgogIHN1YmdyYXBoIGNsdXN0ZXJfaGlkZGVuX2xheWVyIHsKICAgIGxhYmVsID0gJ0hpZGRlbiBMYXllcicKICAgIG4xMSBbbGFiZWwgPSAneUBfezExfScgY29sb3IgPSBibHVlIGZvbnRjb2xvciA9IGJsdWVdCiAgICBuMTIgW2xhYmVsID0gJ3lAX3sxMn0nIGNvbG9yID0gZGFya2dyZWVuIGZvbnRjb2xvciA9IGRhcmtncmVlbl0KICB9CgogIHN1YmdyYXBoIGNsdXN0ZXJfb3V0cHV0X2xheWVyIHsKICAgIGxhYmVsID0gJ091dHB1dCBMYXllcicKICAgIG4yMSBbbGFiZWwgPSAneUBfezJ9J10KICB9CgogIGVkZ2UgW2Fycm93c2l6ZSA9IC4yNV0KCiAgeDEgLT4gbjExIFtsYWJlbCA9ICd3QF97MTExfScgY29sb3IgPSBibHVlIGZvbnRjb2xvciA9IGJsdWVdCiAgeDEgLT4gbjEyIFtsYWJlbCA9ICd3QF97MTEyfScgY29sb3IgPSBkYXJrZ3JlZW4gZm9udGNvbG9yID0gZGFya2dyZWVuXQoKICB4MiAtPiBuMTEgW2xhYmVsID0gJ3dAX3syMTF9JyBjb2xvciA9IGJsdWUgZm9udGNvbG9yID0gYmx1ZV0KICB4MiAtPiBuMTIgW2xhYmVsID0gJ3dAX3syMTJ9JyBjb2xvciA9IGRhcmtncmVlbiBmb250Y29sb3IgPSBkYXJrZ3JlZW5dCgogIHgzIC0+IG4xMSBbbGFiZWwgPSAnd0BfezMxMX0nIGNvbG9yID0gYmx1ZSBmb250Y29sb3IgPSBibHVlXQogIHgzIC0+IG4xMiBbbGFiZWwgPSAnd0BfezMxMn0nIGNvbG9yID0gZGFya2dyZWVuIGZvbnRjb2xvciA9IGRhcmtncmVlbl0KCiAgbjExIC0+IG4yMSBbbGFiZWwgPSAnd0BfezExMjF9J10KICBuMTIgLT4gbjIxIFtsYWJlbCA9ICd3QF97MTIyMX0nXQoKfSIpCmBgYAoKSW4gdGhlIGFib3ZlIGRpYWdyYW0sCiRZX3sxMX0kIGlzIGEgc2luZ2xlIGFkZGl0aXZlIG1vZGVsCgokJApZX3sxMX0gPSBcUGhpKFdfezExMX1YXzEgKyBXX3syMTF9WF8yICsgV197MzExfVhfMykuCiQkCgpTaW1pbGFybHkgJFlfezEyfSQgaXMgYW5vdGhlciBzdWNoIG1vZGVsICh3aXRoIHRoZSBzYW1lIGlucHV0IGZlYXR1cmUgc2V0IGJ1dCBkaWZmZXJlbnQgbW9kZWwgd2VpZ2h0cykKCiQkCllfezEyfSA9IFxQaGkoV197MTEyfVhfMSArIFdfezIxMn1YXzIgKyBXX3szMTJ9WF8zKS4KJCQKCk1vZGVsICRZXzIkIGlzIHlldCBhbm90aGVyIGFkZGl0aXZlIG1vZGVsIGJ1dCB0YWtlcyB0aGUgb3V0cHV0IG9mIHRoZSBhYm92ZSB0d28gbW9kZWxzOgoKJCQKWV8yID0gXFBoaShXX3sxMTIxfVlfezExfSArIFdfezEyMjF9WV97MTJ9KS4KJCQKClRoZSBhYm92ZSBzZXR1cCBpcyBhIHNpbXBsZSBhcmNoaXRlY3R1cmUgb2YgYSBuZXVyYWwgbmV0d29yayBtb2RlbCwKd2l0aCBvbmx5IG9uZSBoaWRkZW4gbGF5ZXIgb2YgdHdvICpuZXVyb25zKi4KKFdlIGFsc28gaWdub3JlIHRoZSBjb25zdGFudC9iaWFzIHRlcm0gaW4gZWFjaCBsYXllciBmb3Igc2ltcGxpY2l0eS4pCkEgbmV1cm9uIGlzIHNpbXBseSBhbiBhZGRpdGl2ZSBtb2RlbCB3aXRoIGEgc28tY2FsbGVkIGFjdGl2YXRpb24gZnVuY3Rpb24gJFxQaGkoXGNkb3QpJCB0byB0cmFuc2Zvcm0gdGhlIG91dHB1dCBmcm9tIGFueSByZWFsIG51bWJlciBpbnRvIGEgc2NhbGVkIHNpZ25hbC4KCk9uZSBub3cgY2FuIGVhc2lseSByZWFsaXplIHRoYXQgYSBsb2dpc3RpYyByZWdyZXNzaW9uIG1vZGVsIGNvdWxkIGJlIHZpZXdlZCBhcyBhIGRlZ2VuZXJhdGVkIG5ldXJhbCBuZXR3b3JrIG1vZGVsIHdpdGggc2luZ2xlIG5ldXJvbiBhbmQgdXNpbmcgc2lnbW9pZCBhcyB0aGUgYWN0aXZhdGlvbiBmdW5jdGlvbi4KQW5kIGEgbGluZWFyIHJlZ3Jlc3Npb24gbW9kZWwgaXMgYSBkZWdlbmVyYXRlZCBuZXVyYWwgbmV0d29yayBtb2RlbCB3aXRoIHNpbmdsZSBuZXVyb24gYW5kIHdpdGhvdXQgYW4gYWN0aXZhdGlvbiBmdW5jdGlvbi4KCiMjIEFjdGl2YXRpb24gRnVuY3Rpb24KCldoeSBkbyB3ZSBuZWVkIHRoZSBhY3RpdmF0aW9uIGZ1bmN0aW9uPwpJbiB0aGUgYWJvdmUgbmV1cmFsIG5ldHdvcmsgbW9kZWwgaW4gdGhlIGFic2VuY2Ugb2YgYWN0aXZhdGlvbiBmdW5jdGlvbiB0aGUgZmluYWwgb3V0cHV0IG1vZGVsICRZXzIkIHdpbGwgZGVnZW5lcmF0ZSBpbnRvIGEgc2ltcGxlIGxpbmVhciBtb2RlbC4KV2UgY2FuIHVzZSBzaW1wbGVyIG5vdGF0aW9ucyB0byBkZW1vbnN0cmF0ZSB0aGlzOgoKJCQKXGJlZ2lue2FsaWduZWR9CnlfMSAmPSBheCArIGIsIFxcCnlfMiAmPSBjeCArIGQsIFxcCnlfMyAmPSBlICsgZnlfMSArIGd5XzIgXFwKJj0gZSArIGYoYXggKyBiKSArIGcoY3ggKyBkKSBcXAomPSBcdW5kZXJicmFjZXsoZSArIGZiICsgZ2QpfV9cdGV4dHtCaWFzfSArIFx1bmRlcmJyYWNleyhmYSArIGdjKX1fXHRleHR7V2VpZ2h0fXguClxlbmR7YWxpZ25lZH0KJCQKCldpdGhvdXQgYWN0aXZhdGlvbiBmdW5jdGlvbiwKbm8gbWF0dGVyIGhvdyBtYW55IG5ldXJvbnMgb3IgbGF5ZXJzIHdlIGRlc2lnbiBmb3Igb3VyIG1vZGVsLAppdCBldmVudHVhbGx5IHJlZHVjZXMgdG8gYSBzaW1wbGUgbGluZWFyIG1vZGVsLgpXaXRoIHRoZSBhY3RpdmF0aW9uIGZ1bmN0aW9uIGFwcGxpZWQgdG8gZWFjaCBuZXVyb24sCnRoZSBtb2RlbCBiZWNvbWVzICpub24tbGluZWFyKiBhbmQgaGVuY2UgY2FuIGhhbmRsZSBtdWNoIG1vcmUgY29tcGxpY2F0ZWQgcGF0dGVybnMgaGlkZGVuIGJlaGluZCB0aGUgZGF0YS4KClNvbWUgcG9wdWxhciBhY3RpdmF0aW9uIGZ1bmN0aW9uczoKCisgW1NpZ21vaWQgKExvZ2lzdGljKV0oaHR0cHM6Ly9lbi53aWtpcGVkaWEub3JnL3dpa2kvTG9naXN0aWNfZnVuY3Rpb24pCisgW1RhbmggKEh5cGVyYm9saWMgVGFuZ2VudCldKGh0dHBzOi8vZW4ud2lraXBlZGlhLm9yZy93aWtpL0h5cGVyYm9saWNfZnVuY3Rpb24jSHlwZXJib2xpY190YW5nZW50KQorIFtSZUxVIChSZWN0aWZpZWQgTGluZWFyIFVuaXQpXShodHRwczovL2VuLndpa2lwZWRpYS5vcmcvd2lraS9SZWN0aWZpZXJfKG5ldXJhbF9uZXR3b3JrcykpCisgU3dpc2g6ICRmKHgpID0geCBcY2RvdCBcbWJveHtzaWdtb2lkfSh4KSQsIHByb3Bvc2VkIGJ5IFtHb29nbGUgQnJhaW5dKGh0dHBzOi8vYWkuZ29vZ2xlL3Jlc2VhcmNoL3RlYW1zL2JyYWluLykKCiMjIEJhY2twcm9wYWdhdGlvbgoKVG8gc29sdmUgZm9yIG1vZGVsIHdlaWdodHMgaW4gYSBuZXVyYWwgbmV0d29yaywKd2UgdXNlIGEgdGVjaG5pcXVlIGNhbGxlZCBiYWNrcHJvcGFnYXRpb24gd2hpY2ggaXMgZXNzZW50aWFsbHkgYW4gaXRlcmF0aXZlIHByb2Nlc3Mgb2YgZ3JhZGllbnQgZGVzY2VudC4KClRvIHNpbXBsaWZ5IG5vdGF0aW9uIHdlIGFzc3VtZSBlYWNoIG5ldXJvbiBpcyBzaW1wbHkgYSB1bml2YXJpYXRlIG1vZGVsLgpDb25zaWRlciB0aGUgZm9sbG93aW5nIG1pbmltdW0gYXJjaGl0ZWN0dXJlOgoKYGBge3Igc2ltcGxpZmllZF9ubl9kaWFncmFtLCBlY2hvPUZBTFNFfQpEaWFncmFtbWVSOjpnclZpeigiCmRpZ3JhcGggc3Vic2NyaXB0IHsKCiAgZ3JhcGggW2xheW91dCA9IGRvdCByYW5rZGlyID0gTFIgb3JkZXJpbmcgPSBpbiByYW5rc2VwPTJdCgogIG5vZGUgW3NoYXBlID0gY2lyY2xlXQoKICB4MCBbbGFiZWwgPSAnMSddCiAgeDEgW2xhYmVsID0gJ3gnXQogIHowIFtsYWJlbCA9ICcxJ10KICB6MSBbbGFiZWwgPSAneiddCiAgeSAgW2xhYmVsID0gJ3knXQoKICBlZGdlIFthcnJvd3NpemUgPSAuMjVdCgogIHgwIC0+IHoxIFtsYWJlbCA9ICdiQF97MH0nXQogIHgxIC0+IHoxIFtsYWJlbCA9ICd3QF97MH0nXQogIHowIC0+IHkgIFtsYWJlbCA9ICdiQF97MX0nXQogIHoxIC0+IHkgIFtsYWJlbCA9ICd3QF97MX0nXQoKfSIpCmBgYAoKTWF0aGVtYXRpY2FsbHk6CgokJApcYmVnaW57YWxpZ25lZH0KXGhhdHt5fSAKJj0gXFBoaShiXzEgKyB3XzF6KSBcXAomPSBcUGhpKGJfMSArIHdfMVxQaGkoYl8wICsgd18weCkpLApcZW5ke2FsaWduZWR9CiQkCgp3aGVyZQoKJCQKeiA9IFxQaGkoYl8wICsgd18weCksCiQkCgphbmQKCiQkClxQaGkodCkgPSBcZnJhY3sxfXsxICsgZV57LXR9fS4KJCQKCiMjIyBNU0UgTG9zcwoKVGhvdWdoIGl0IG1heSBub3QgYmUgdmVyeSBtZWFuaW5nZnVsIHRvIHVzZSBNU0UgbG9zcyB3aGVuIHRoZSBvdXRwdXQgbGF5ZXIgaXMgYXBwbGllZCB3aXRoIGFuIGFjdGl2YXRpb24gZnVuY3Rpb24sCndlIGNhbiBzdGlsbCBkbyBpdCBmb3IgZWR1Y2F0aW9uYWwgcHVycG9zZS4KCiQkClxtYm94e01TRS1Mb3NzfSA9IFxmcmFjezF9e059XHN1bV9pXk4gICh5X2kgLSBcaGF0e3l9X2kpXjIuCiQkCgpGaXJzdGx5IHdlIHRha2UgdGhlIGRlcml2YXRpdmUgdy5yLnQuIHRoZSB3ZWlnaHQgaW4gdGhlIGxhc3QgbGF5ZXI6CgokJApcYmVnaW57YWxpZ25lZH0KXGZyYWN7XHBhcnRpYWwgXG1ib3h7TVNFLUxvc3N9fXtccGFydGlhbCB3XzF9CiY9IC0gXGZyYWN7MX17Tn1cc3VtX2kgKHlfaSAtIFxoYXR7eX1faSlcZnJhY3tccGFydGlhbCBcaGF0e3l9X2l9e1xwYXJ0aWFsIHdfMX0gXFwKJj0gLSBcZnJhY3sxfXtOfVxzdW1faSAoeV9pIC0gXGhhdHt5fV9pKQpcdW5kZXJicmFjZXsgIFxmcmFje1xwYXJ0aWFsIHR9e1xwYXJ0aWFsIHdfMX1cZnJhY3tccGFydGlhbCBcUGhpKHQpfXtccGFydGlhbCB0fSB9X3t0ID0gYl8xICsgd18xXFBoaShiXzAgKyB3XzB4KX1cXAomPSAtIFxmcmFjezF9e059XHN1bV9pICh5X2kgLSBcaGF0e3l9X2kpIFxjZG90IFxQaGkodCkoMSAtIFxQaGkodCkpIFxjZG90IHpfaS4KXGVuZHthbGlnbmVkfQokJAoKU2ltaWxhcmx5IGZvciB0aGUgYmlhcyBpbiB0aGUgbGFzdCBsYXllcjoKCiQkClxmcmFje1xwYXJ0aWFsIFxtYm94e01TRS1Mb3NzfX17XHBhcnRpYWwgYl8xfSA9IC0gXGZyYWN7MX17Tn1cc3VtX2kgKHlfaSAtIFxoYXR7eX1faSkgXGNkb3QgXFBoaSh0KSgxIC0gXFBoaSh0KSkuCiQkCgpOb3cgbW92ZSBvbiB0byB0aGUgYmlhcyBhbmQgd2VpZ2h0IGluIHRoZSBmaXJzdCBsYXllcjoKCiQkClxiZWdpbnthbGlnbmVkfQpcZnJhY3tccGFydGlhbCBcbWJveHtNU0UtTG9zc319e1xwYXJ0aWFsIHdfMH0KJj0gLSBcZnJhY3sxfXtOfVxzdW1faSAoeV9pIC0gXGhhdHt5fV9pKVxmcmFje1xwYXJ0aWFsIFxoYXR7eX1faX17XHBhcnRpYWwgd18wfSBcXAomPSAtIFxmcmFjezF9e059XHN1bV9pICh5X2kgLSBcaGF0e3l9X2kpClx1bmRlcmJyYWNleyAgXGZyYWN7XHBhcnRpYWwgdH17XHBhcnRpYWwgd18wfVxmcmFje1xwYXJ0aWFsIFxQaGkodCl9e1xwYXJ0aWFsIHR9IH1fe3QgPSBiXzEgKyB3XzFcUGhpKGJfMCArIHdfMHgpfVxcCiY9IC0gXGZyYWN7MX17Tn1cc3VtX2kgKHlfaSAtIFxoYXR7eX1faSkgXGNkb3QgXFBoaSh0KSgxIC0gXFBoaSh0KSkgXGNkb3QgClx1bmRlcmJyYWNleyBcUGhpKGspKDEgLSBcUGhpKGspKSB9X3trID0gYl8wICt3XzB4fSBcY2RvdCB3XzEgXGNkb3QgeF9pLCBcXApcZnJhY3tccGFydGlhbCBcbWJveHtNU0UtTG9zc319e1xwYXJ0aWFsIGJfMH0gCiY9IC0gXGZyYWN7MX17Tn1cc3VtX2kgKHlfaSAtIFxoYXR7eX1faSkgXGNkb3QgXFBoaSh0KSgxIC0gXFBoaSh0KSkgXGNkb3QgXFBoaShrKSgxIC0gXFBoaShrKSkuClxlbmR7YWxpZ25lZH0KJCQKCk9uZSBjYW4gY2xlYXJseSBzZWUgdGhlcmUgaXMgYSBsaW5rYWdlIGJldHdlZW4gdGhlIGRlcml2YXRpdmUgb2YgdGhlIHdlaWdodHMgaW4gY29uc2VjdXRpdmUgbGF5ZXJzOgoKJCQKXGJlZ2lue2FsaWduZWR9ClxmcmFje1xwYXJ0aWFsIFxtYm94e01TRS1Mb3NzfX17XHBhcnRpYWwgd18xfQomPSAtIFxmcmFjezF9e059XHN1bV9pICh5X2kgLSBcaGF0e3l9X2kpIFxjZG90IFxQaGkodCkoMSAtIFxQaGkodCkpIFxjZG90IHpfaSwgXFwKXGZyYWN7XHBhcnRpYWwgXG1ib3h7TVNFLUxvc3N9fXtccGFydGlhbCB3XzB9CiY9IC0gXGZyYWN7MX17Tn1cc3VtX2kgKHlfaSAtIFxoYXR7eX1faSkgXGNkb3QgClx1bmRlcmJyYWNle1xQaGkodCkoMSAtIFxQaGkodCkpfV97XGhhdHt5fV9pKDEgLSBcaGF0e3l9X2kpfSBcY2RvdCAKXHVuZGVyYnJhY2V7XFBoaShrKSgxIC0gXFBoaShrKSkgXGNkb3Qgd18xIFxjZG90IHhfaX1fe1xmcmFje1xwYXJ0aWFsIHdfMXp9e1xwYXJ0aWFsIHdfMH0gPSBcZnJhY3tccGFydGlhbCB3XzFcUGhpKGIwICsgd18weCl9e1xwYXJ0aWFsIHdfMH19LgpcZW5ke2FsaWduZWR9CiQkCgojIyMgQ3Jvc3MtRW50cm9weSBMb3NzCgpTaW1pbGFybHkgd2UgY2FuIGRlcml2ZSB0aGUgZ3JhZGllbnRzIGZvciBjcm9zcy1lbnRyb3B5IGxvc3MuCgokJApcYmVnaW57YWxpZ25lZH0KXG1ib3h7TG9nTG9zc30gCiY9IC0gXGZyYWN7MX17Tn1cc3VtX2leTiBcYmlnZ1sgeV9pXGxuXGhhdHt5fV9pICsgKDEgLSB5X2kpXGxuKDEgLSBcaGF0e3l9X2kpXGJpZ2ddLCBcXApcZnJhY3tccGFydGlhbCBcbWJveHtMb2dMb3NzfX17XHBhcnRpYWwgd18xfQomPSAtIFxmcmFjezF9e059IFxzdW1faSAoeV9pIC0gXGhhdHt5fV9pKXpfaSwgXFwKXGZyYWN7XHBhcnRpYWwgXG1ib3h7TG9nTG9zc319e1xwYXJ0aWFsIHdfMH0KJj0gLSBcZnJhY3sxfXtOfSBcc3VtX2kgKHlfaSAtIFxoYXR7eX1faSlcUGhpKGspKDEgLSBcUGhpKGspKXdfMXhfaS5cXApcZW5ke2FsaWduZWR9CiQkCgooU2tpcCB0aGUgYmlhcyB0ZXJtcyB0byBzYXZlIHNwYWNlLikKCk5vdyBsZXQncyBpbXBsZW1lbnQgdGhlIHNpbXBsZSBuZXVyYWwgbmV0d29yayBtb2RlbCBpbiBQeXRob246CgpgYGB7cHl0aG9uIG5ufQpkZWYgc2lnbW9pZCh4KToKICByZXR1cm4gbnAuZXhwKC1ucC5sb2dhZGRleHAoMCwgLXgpKQoKCmRlZiBzaWdtb2lkX2dyYWQoeik6CiAgcmV0dXJuIHoqKDEgLSB6KQoKCmNsYXNzIE5ldXJhbE5ldHdvcms6CiAgIiIiU2ltcGxlIG5ldXJhbCBuZXR3b3JrIHdpdGggMSBoaWRkZW4gbGF5ZXIgb2YgNCBuZXVyb25zLiIiIgogIGRlZiBfX2luaXRfXyhzZWxmLCB4LCB5KToKICAgIHNlbGYuaW5wdXQgPSB4CiAgICBzZWxmLncxID0gbnAucmFuZG9tLnJhbmQoc2VsZi5pbnB1dC5zaGFwZVsxXSwgNCkKICAgIHNlbGYudzIgPSBucC5yYW5kb20ucmFuZCg0LCAxKQogICAgc2VsZi55ID0geQogICAgc2VsZi5vdXRwdXQgPSBucC56ZXJvcyh5LnNoYXBlKQoKICBkZWYgZmVlZGZvcndhcmQoc2VsZik6CiAgICBzZWxmLmxheWVyMSA9IHNpZ21vaWQobnAuZG90KHNlbGYuaW5wdXQsIHNlbGYudzEpKQogICAgc2VsZi5vdXRwdXQgPSBzaWdtb2lkKG5wLmRvdChzZWxmLmxheWVyMSwgc2VsZi53MikpCgogIGRlZiBiYWNrcHJvcChzZWxmLCBscik6CiAgICByYWlzZSBOb3RJbXBsZW1lbnRlZEVycm9yCiAgCiAgZGVmIHRyYWluKHNlbGYsIGxyLCBuX3N0ZXApOgogICAgZm9yIHN0ZXAgaW4gcmFuZ2Uobl9zdGVwKToKICAgICAgc2VsZi5mZWVkZm9yd2FyZCgpCiAgICAgIHNlbGYuYmFja3Byb3AobHI9bHIpCiAgICAgIHloYXQgPSAiLCIuam9pbihbc3RyKHkpIGZvciB5IGluIG5wLnNxdWVlemUoc2VsZi5vdXRwdXQpXSkKICAgIHJldHVybiB5aGF0CgoKY2xhc3MgTmVydWFsTmV0d29ya1dpdGhNU0VMb3NzKE5ldXJhbE5ldHdvcmspOgogIGRlZiBiYWNrcHJvcChzZWxmLCBscik6CiAgICAjIFdlIGlnbm9yZSBhbGwgY29uc3RhbnQgdGVybXMgaW4gdGhlIGdyYWRpZW50LgogICAgc2VsZi5keSA9IHNlbGYueSAtIHNlbGYub3V0cHV0CiAgICBkdzIgPSAtIG5wLmRvdChzZWxmLmxheWVyMS5ULCAoc2VsZi5keSpzaWdtb2lkX2dyYWQoc2VsZi5vdXRwdXQpKSkKICAgIGR3MSA9IC0gbnAuZG90KHNlbGYuaW5wdXQuVCwgCiAgICAgICAgICAgICAgICAgICAobnAuZG90KHNlbGYuZHkqc2lnbW9pZF9ncmFkKHNlbGYub3V0cHV0KSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgc2VsZi53Mi5UKSpzaWdtb2lkX2dyYWQoc2VsZi5sYXllcjEpKSkKICAgIHNlbGYudzEgLT0gbHIgKiBkdzEKICAgIHNlbGYudzIgLT0gbHIgKiBkdzIKCgpjbGFzcyBOZXJ1YWxOZXR3b3JrV2l0aExvZ0xvc3MoTmV1cmFsTmV0d29yayk6CiAgZGVmIGJhY2twcm9wKHNlbGYsIGxyKToKICAgICMgV2UgaWdub3JlIGFsbCBjb25zdGFudCB0ZXJtcyBpbiB0aGUgZ3JhZGllbnQuCiAgICBzZWxmLmR5ID0gc2VsZi55IC0gc2VsZi5vdXRwdXQKICAgIGR3MiA9IC0gbnAuZG90KHNlbGYubGF5ZXIxLlQsIHNlbGYuZHkpCiAgICBkdzEgPSAtIG5wLmRvdChzZWxmLmlucHV0LlQsIAogICAgICAgICAgICAgICAgICAgbnAuZG90KHNlbGYuZHksIHNlbGYudzIuVCkqc2lnbW9pZF9ncmFkKHNlbGYubGF5ZXIxKSkKICAgIHNlbGYudzEgLT0gbHIgKiBkdzEKICAgIHNlbGYudzIgLT0gbHIgKiBkdzIKYGBgCgpIZXJlIHdlIHdpbGwgdXNlIHRoZSBoZWxsby13b3JsZCBleGFtcGxlIG9mIGFydGlmaWNpYWwgbmV1cmFsIG5ldHdvcms6ClRoZSBbWE9SXShodHRwczovL2VuLndpa2lwZWRpYS5vcmcvd2lraS9YT1JfZ2F0ZSkgcHJvYmxlbS4KVGhlIFhPUiBsb2dpY2FsIG91dGNvbWUsCmJlc2lkZXMgZXh0cmVtZWx5IHNpbXBsZSwKaXMgbm90IGxpbmVhcmx5IHNlcGFyYWJsZS4KU28gaXQgc2VydmVzIGFzIGEgZ29vZCBleGFtcGxlIG9mIHNob3djYXNpbmcgbmV1cmFsIG5ldHdvcmtzJyBub24tbGluZWFyaXR5LgoKVGhlIGlucHV0IGRhdGEgaXMgc2ltcGx5IGNvbWJpbmF0aW9uIG9mIHR3byBiaW5hcnkgc3dpdGNoZXMuCihGb3IgY29tcGxldGVuZXNzIHdlIGFsc28gaW5jbHVkZSBhIGNvbnN0YW50IHRlcm0gd2hpY2ggYWx3YXlzIGV2YWx1YXRlIHRvIDEgYXMgdGhlIGZpcnN0IGZlYXR1cmUuKQpUaGUgb3V0cHV0IGRhdGEgaXMgdGhlIFhPUiByZXN1bHQuCgpgYGB7cHl0aG9uIG5uX3hvcl9kYXRhfQpYID0gbnAuYXJyYXkoCiAgICBbWzEsIDAsIDBdLAogICAgIFsxLCAxLCAwXSwKICAgICBbMSwgMCwgMV0sCiAgICAgWzEsIDEsIDFdXSkKeSA9IG5wLmFycmF5KFtbMF0sIFsxXSwgWzFdLCBbMF1dKQoKcHJpbnQoWCkgICMgSW5wdXQgZmVhdHVyZXM6IEJpYXMgKyB0d28gYmluYXJ5IHN3aXRjaGVzLgpwcmludCh5KSAgIyBYT1Igb3V0cHV0LgpgYGAKCk5vdyBsZXQncyBzZWUgaWYgb3VyIHNpbXBsZSBuZXVyYWwgbmV0d29yayBtb2RlbCBjYW4gbGVhcm4gdGhlIFhPUiBwYXR0ZXJuLgoKYGBge3B5dGhvbiBubl9nZF9tc2VfbG9zc30Kbm5fbXNlID0gTmVydWFsTmV0d29ya1dpdGhNU0VMb3NzKFgsIHkpCm5uX21zZS50cmFpbihscj0xLCBuX3N0ZXA9MzAwMCkgICMgVGhlIHByZWRpY3RlZCBYT1Igb3V0Y29tZS4KcHJpbnQobm5fbXNlLncxKSAgIyBFc3RpbWF0ZWQgMXN0LWxheWVyIG1vZGVsIHdlaWdodHMKcHJpbnQobm5fbXNlLncyKSAgIyBFc3RpbWF0ZWQgMm5kLWxheWVyIG1vZGVsIHdlaWdodHMKYGBgCgpgYGB7cHl0aG9uIG5uX2dkX2xvZ19sb3NzfQpubl9sb2dsb3NzID0gTmVydWFsTmV0d29ya1dpdGhMb2dMb3NzKFgsIHkpCm5uX2xvZ2xvc3MudHJhaW4obHI9MSwgbl9zdGVwPTMwMDApCmBgYAoKRm9yIHRoaXMgc2ltcGxlIGV4YW1wbGUsCmJvdGggTVNFIGFuZCBjcm9zcy1lbnRyb3B5IGxvc3MgY2FuIHdvcmsgZmluZSB0byBmaWd1cmUgb3V0IHRoZSBYT1IgcGF0dGVybi4KKFN0cmljdGx5IHNwZWFraW5nIGNyb3NzLWVudHJvcHkgbG9zcyBwZXJmb3JtcyBiZXR0ZXIuKQoKIyMgUmVndWxhcml6YXRpb24KCiMjIyBMMi1Ob3JtCgojIyMgTDEtTm9ybQoKIyMjIERyb3BvdXQKCgo=